欢乐的周末(C++ )刷题记录
2023题库目录
链接2023华为OD备考【转载】
题目描述
小华和小为是很要好的朋友,他们约定周末一起吃饭。
通过手机交流,他们在地图上选择了多个聚餐地点(由于自然地形等原因,部分聚餐地点不可达),求小华和小为都能到达的聚餐地点有多少个?
输入描述
第一行输入m和n,m代表地图的长度,n代表地图的宽度。
第二行开始具体输入地图信息,地图信息包含:
0 为通畅的道路
1 为障碍物(且仅1为障碍物)
2 为小华或者小为,地图中必定有且仅有2个 (非障碍物)
3 为被选中的聚餐地点(非障碍物)
输出描述
可以被两方都到达的聚餐地点数量,行末无空格。
用例
输入 | 4 4 2 1 0 3 0 1 2 1 0 3 0 0 0 0 0 0 |
输出 | 2 |
说明 | 第一行输入地图的长宽为3和4。 第二行开始为具体的地图,其中:3代表小华和小明选择的聚餐地点;2代表小华或者小明(确保有2个);0代表可以通行的位置;1代表不可以通行的位置。 此时两者能都能到达的聚餐位置有2处。 |
输入 | 4 4 2 1 2 3 0 1 0 0 0 1 0 0 0 1 0 0 |
输出 | 0 |
说明 | 第一行输入地图的长宽为4和4。 第二行开始为具体的地图,其中:3代表小华和小明选择的聚餐地点;2代表小华或者小明(确保有2个);0代表可以通行的位置;1代表不可以通行的位置。 由于图中小华和小为之间有个阻隔,此时,没有两人都能到达的聚餐地址,故而返回0。 |
备注:
地图的长宽为m和n,其中:
4 <= m <= 100
4 <= n <= 100
聚餐的地点数量为 k,则
1< k <= 100
C++
#include <iostream>
#include <vector>
using namespace std;
// 并查集实现
class UnionFindSet {
private:
vector<int> fa;
public:
UnionFindSet(int n) {
fa.resize(n);
for (int i = 0; i < n; i++) fa[i] = i;
}
int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]);
return fa[x];
}
return x;
}
void merge(int x, int y) {
int x_fa = find(x);
int y_fa = find(y);
if (x_fa != y_fa) {
fa[y_fa] = x_fa;
}
}
};
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> matrix(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matrix[i][j];
}
}
UnionFindSet ufs(n * m);
vector<int> huawei; // 记录小华位置
vector<int> restaurants; // 记录聚餐地点位置
vector<vector<int>> offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 偏移量
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] != 1) { // 如果是障碍物则不处理
int x = i * m + j; // 将二维坐标转换为一维坐标
if (matrix[i][j] == 2) huawei.push_back(x); // 记录小华位置
else if (matrix[i][j] == 3) restaurants.push_back(x); // 记录聚餐地点位置
for (auto offset : offsets) { // 遍历四个方向
int newI = i + offset[0];
int newJ = j + offset[1];
if (newI >= 0 && newI < n && newJ >= 0 && newJ < m && matrix[newI][newJ] != 1) {
ufs.merge(x, newI * m + newJ); // 合并连通块
}
}
}
}
}
int hua_fa = ufs.find(huawei[0]); // 获取小华所在连通块的祖先
int wei_fa = ufs.find(huawei[1]); // 获取小为所在连通块的祖先
if (hua_fa != wei_fa) { // 如果小华和小为不在同一个连通块中,说明没有共同到达的聚餐地点
cout << 0 << endl;
return 0;
}
int ans = 0;
for (auto restaurant : restaurants) { // 遍历所有聚餐地点
if (ufs.find(restaurant) == hua_fa) { // 如果聚餐地点和小华在同一个连通块中
ans++; // 答案加一
}
}
cout << ans << endl; // 输出答案
return 0;
}
#华为信息集散地#