突发奇想
  • 板块B3625 迷宫寻路
  • 楼主cgxd
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/10 17:08
  • 上次更新2024/8/10 18:34:19
查看原帖
突发奇想
1272259
cgxd楼主2024/8/10 17:08

这题是不是也能用并查集做?

#include<bits/stdc++.h>
using namespace std;
int n, m, f[10005];
vector<string> v(1);
int id(int i, int j){
	return (i - 1) * m + j;
}int find(int x){
	return f[x] == x? x: f[x] = find(f[x]);
}void uni(int x, int y){
	f[find(x)] = find(y);
}signed main(){
	scanf("%d%d", &n, &m);
	iota(f, f + n * m + 1, 0);
	for(int i = 1; i <= n; ++i){
		string s;
		cin >> s;
		v.push_back(string(1, ' ') + s);
	}for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(v[i][j] == '#')
				continue;
			if(i != n and v[i + 1][j] == '.')
				uni(id(i, j), id(i + 1, j));
			if(j != m and v[i][j + 1] == '.')
				uni(id(i, j), id(i, j + 1));
			if(i != 1 and v[i - 1][j] == '.')
				uni(id(i, j), id(i - 1, j));
			if(j != 1 and v[i][j - 1] == '.')
				uni(id(i, j), id(i, j - 1));
		}
	}printf("%s", find(1) == find(n * m)? "Yes": "No");
	return 0;
}
2024/8/10 17:08
加载中...