CSP-201912-2-回收站选址

【50分思路-暴力枚举】

#include <iostream>    
#include <vector>
#include <algorithm>
using namespace std;
struct trashPoint
{int x; int y;
};
vector<trashPoint>trashList;
vector<int>grade(5);
int main() {int n, max_x = -1, max_y = -1, min_x = 999, min_y = 999;cin >> n;for (int i = 0; i < n; i++){trashPoint t;cin >> t.x >> t.y;max_x = max(max_x, t.x), max_y = max(max_y, t.y);min_x = min(min_x, t.x), min_y = min(min_y, t.y);trashList.push_back(t);}int deltaX = max_x - min_x, deltaY = max_y - min_y; int moveX = min_x, moveY = min_y;vector<vector<bool>>tashMatrix(deltaX + 1, vector<bool>(deltaY + 1));for (const auto& it : trashList){tashMatrix[it.x - moveX][it.y - moveY] = 1;}for (int i = 1; i < deltaX; i++){for (int j = 1; j < deltaY; j++){int myGrade = 0;if (tashMatrix[i][j] && tashMatrix[i][j + 1] && tashMatrix[i][j - 1] && tashMatrix[i + 1][j] && tashMatrix[i - 1][j]){if (tashMatrix[i - 1][j - 1])myGrade++;if (tashMatrix[i + 1][j + 1])myGrade++;if (tashMatrix[i - 1][j + 1])myGrade++;if (tashMatrix[i + 1][j - 1])myGrade++;grade[myGrade]++;}}}for (const auto& it : grade) {cout << it << endl;}return 0;
}

【100分思路】

1. 读取数据：初始化一个二维向量 coords 存储每个垃圾点的坐标。对于每个垃圾点，代码读取其横纵坐标 (x, y) 并存储在 coords 中。

2. 计算相邻点数量：对于每个垃圾点，代码计算其直接相邻的垃圾点数量（即上下左右四个方向）。这是通过比较每个点与其他所有点的坐标来完成的，如果两个点在水平或垂直方向上相邻（差一个单位距离），则它们被认为是相邻的。对于每个点，它的相邻垃圾点的数量被记录在 adjacentCount 向量中。

3. 评分回收站选址：根据题目的要求，一个地点适合建立回收站的条件是它有四个直接相邻的垃圾点。对于每个符合这一条件的垃圾点，代码会进一步检查其四个对角线方向上的垃圾点的数量。对角线上的垃圾点数量将决定该地点的评分，评分范围是 0 到 4。每个可能的评分值都有一个对应的计数，记录在 diagonalCounts 向量中。

4. 输出结果：最后，代码输出每个评分值的回收站选址数量。对于每个从 0 到 4 的评分值，它打印出相应的计数值，这些值表示评分为该值的合适回收站选址的数量。

完整代码

#include<iostream> 
#include<vector> 
using namespace std;int main() {int n; cin >> n; vector<vector<long long>> coords(n, vector<long long>(2)); // 二维向量存储坐标vector<int> adjacentCount(n, 0); // 创建一个向量存储每个点相邻点的数量vector<int> diagonalCounts(5, 0); // 创建一个向量存储对角线上点的数量分布// 读取坐标数据for (int i = 0; i < n; i++) {cin >> coords[i][0] >> coords[i][1]; // 读取每个坐标}// 计算每个点的相邻点数量for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 检查是否为相邻点（水平或垂直相邻）if ((coords[i][0] == coords[j][0] && abs(coords[i][1] - coords[j][1]) == 1) ||(coords[i][1] == coords[j][1] && abs(coords[i][0] - coords[j][0]) == 1)) {adjacentCount[i]++;adjacentCount[j]++;}}}// 统计每个点对角线上的点的数量for (int i = 0; i < n; i++) {int diagCount = 0; // 对角线上的点数量if (adjacentCount[i] == 4) { // 如果一个点有4个相邻点，则检查其对角线上的点for (int j = 0; j < n; j++) {// 检查是否为对角线上的点if (abs(coords[i][0] - coords[j][0]) == 1 && abs(coords[i][1] - coords[j][1]) == 1) {diagCount++;}}diagonalCounts[diagCount]++; // 根据对角线上的点的数量增加对应的计数}}for (int i = 0; i <= 4; i++) {cout << diagonalCounts[i] << endl; }return 0; // 程序结束
}