Loading [MathJax]/extensions/tex2jax.js

P1141:01迷宫题解

思路

在我思考了很久之后(其实是理解题解),我解决了这道题的做法。主要就是并查集的一个扩展和预处理。我们在读取01迷宫时,就检测左边的点和右边的点是否连通。如果是连通的话,在并查集中合并,并且在并查集中把连通块个数相加即可

还有一个主要的思想就是映射。在并查集中我们的数组是一维的(mem[]),我们只需要一个计算函数把(x,y)转换成数字即可。(具体的:ret = x*n + y;

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 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)所以行数可能比较多。

Leave a Reply

Your email address will not be published. Required fields are marked *