思路
在我思考了很久之后(其实是理解题解),我解决了这道题的做法。主要就是并查集的一个扩展和预处理。我们在读取01迷宫时,就检测左边的点和右边的点是否连通。如果是连通的话,在并查集中合并,并且在并查集中把连通块个数相加即可。
还有一个主要的思想就是映射。在并查集中我们的数组是一维的(mem[]
),我们只需要一个计算函数把(x,y
)转换成数字即可。(具体的:ret = x*n + y;
)
代码
// P1141_ufs.cpp
#include <iostream>
using namespace std;
const int maxm = 10000000;
const int maxn = 1010;
char map[maxn][maxn];
int n, m;
struct UFS
{
int mem[maxm];
int mem_h[maxm];
UFS()
{
for (int i = 0; i < maxm; i++)
mem[i] = i, mem_h[i] = 1;
for (int i = maxm; i < maxn; i++)
mem_h[i] = 1;
}
int Find(int a)
{
if (mem[a] == a)
return a;
return mem[a] = Find(mem[a]);
}
void Unite(int a, int b)
{
if (Find(a) != Find(b))
mem_h[Find(a)] += mem_h[Find(b)], mem[Find(b)] = Find(a);
}
} u;
int hashcode(int a, int b)
{
return a * n + b;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> map[i][j];
// left;
if (j != 1 && map[i][j - 1] != map[i][j])
u.Unite(hashcode(i, j), hashcode(i, j - 1));
// up;
if (i != 1 && map[i - 1][j] != map[i][j])
u.Unite(hashcode(i, j), hashcode(i - 1, j));
}
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
cout << u.mem_h[u.Find(hashcode(a, b))] << endl;
}
return 0;
}
// P1141_ufs.cpp
#include <iostream>
using namespace std;
const int maxm = 10000000;
const int maxn = 1010;
char map[maxn][maxn];
int n, m;
struct UFS
{
int mem[maxm];
int mem_h[maxm];
UFS()
{
for (int i = 0; i < maxm; i++)
mem[i] = i, mem_h[i] = 1;
for (int i = maxm; i < maxn; i++)
mem_h[i] = 1;
}
int Find(int a)
{
if (mem[a] == a)
return a;
return mem[a] = Find(mem[a]);
}
void Unite(int a, int b)
{
if (Find(a) != Find(b))
mem_h[Find(a)] += mem_h[Find(b)], mem[Find(b)] = Find(a);
}
} u;
int hashcode(int a, int b)
{
return a * n + b;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> map[i][j];
// left;
if (j != 1 && map[i][j - 1] != map[i][j])
u.Unite(hashcode(i, j), hashcode(i, j - 1));
// up;
if (i != 1 && map[i - 1][j] != map[i][j])
u.Unite(hashcode(i, j), hashcode(i - 1, j));
}
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
cout << u.mem_h[u.Find(hashcode(a, b))] << endl;
}
return 0;
}
// P1141_ufs.cpp #include <iostream> using namespace std; const int maxm = 10000000; const int maxn = 1010; char map[maxn][maxn]; int n, m; struct UFS { int mem[maxm]; int mem_h[maxm]; UFS() { for (int i = 0; i < maxm; i++) mem[i] = i, mem_h[i] = 1; for (int i = maxm; i < maxn; i++) mem_h[i] = 1; } int Find(int a) { if (mem[a] == a) return a; return mem[a] = Find(mem[a]); } void Unite(int a, int b) { if (Find(a) != Find(b)) mem_h[Find(a)] += mem_h[Find(b)], mem[Find(b)] = Find(a); } } u; int hashcode(int a, int b) { return a * n + b; } int main() { ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin >> map[i][j]; // left; if (j != 1 && map[i][j - 1] != map[i][j]) u.Unite(hashcode(i, j), hashcode(i, j - 1)); // up; if (i != 1 && map[i - 1][j] != map[i][j]) u.Unite(hashcode(i, j), hashcode(i - 1, j)); } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; cout << u.mem_h[u.Find(hashcode(a, b))] << endl; } return 0; }
代码我喜欢强格式化(vscode)所以行数可能比较多。