01迷宫

题目描述

有一个仅由数字 $0$ 与 $1$ 组成的 $n \times n$ 格迷宫。若你位于一格 $0$ 上，那么你可以移动到相邻 $4$ 格中的某一格 $1$ 上，同样若你位于一格 $1$ 上，那么你可以移动到相邻 $4$ 格中的某一格 $0$ 上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式

第一行为两个正整数 $n,m$。

下面 $n$ 行，每行 $n$ 个字符，字符只可能是 $0$ 或者 $1$，字符之间没有空格。

接下来 $m$ 行，每行两个用空格分隔的正整数 $i,j$，对应了迷宫中第 $i$ 行第 $j$ 列的一个格子，询问从这一格开始能移动到多少格。

输出格式

$m$ 行，对于每个询问输出相应答案。

样例 #1

样例输入 #1

1
2
3
4
5
2 2
01
10
1 1
2 2

样例输出 #1

1
2
4
4

提示

对于样例，所有格子互相可达。

  • 对于 $20%$ 的数据，$n \leq 10$；
  • 对于 $40%$ 的数据，$n \leq 50$；
  • 对于 $50%$ 的数据，$m \leq 5$；
  • 对于 $60%$ 的数据，$n,m \leq 100$；
  • 对于 $100%$ 的数据，$1\le n \leq 1000$，$1\le m \leq 100000$。

分析

看到本题的第一反应是用dfs求出每个连通块的点的个数，则连通块中的每个点的可达点个数就是连通块的大小。

样例：

1
2
01
10

对于样例我们可以看到每个点之间都是相互可达的，故只有一个连通块，大小为4，所以每个点的可达点个数都是4。

实现

普通DFS

一开始我直接只用DFS来求每个连通块的大小，并在搜索完该连通块中的一个点后，把所有点的可达个数都改成改连通块大小，在下次询问时可直接返回结果。最大时间复杂度是$O(n^2)$，最大深度也说$O(n^2)$，数据是$1000$，很不幸出现RE了。

用并查集进行优化

不过加上并查集进行优化后进可以AC了。

这里回顾一下并查集的代码

[并查集模板题]:AcWing 836. 合并集合 - AcWing

并查集模板代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;
const int N = 1e5+10;
int n,m,p[N];
int find(int x)
{
    return x==p[x]?x:p[x]=find(p[x]);
}
void Union(int a,int b)
{
    int h1=find(a),h2=find(b);
    if(h1!=h2)
    {
        p[h2]=h1;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    while(m--)
    {
        char op[2]; 
        int a,b;
        cin>>op>>a>>b;
        if(*op=='M')
        {
            Union(a,b);
        }
        else
        {
            if(find(a)==find(b))
            puts("Yes");
            else
            puts("No");
        }
    }
}

而对于这道题就可以把每个相互可达的点放在一个并查集中，当每次搜索时都把两个相邻的并查集连接同时更新并查集的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =1e6+100;
const int M =1010;
int f[N],p[N],n,m;//f[i]代表第i个点的子节点数+1(加上自己)，p[i]代表第i个点的父节点。
char g[M][M];
int find(int x)
{
    return x==p[x]?x:p[x]=find(p[x]);
}
//把b的祖宗节点连到a的祖宗节点上
void Union(int a,int b)
{
    int h1=find(a),h2=find(b);
    if(h1!=h2)
    {
        p[h2]=h1;
        f[h1]+=f[h2];
    }
}
//dfs返回的是点(x,y)的祖宗节点，在找祖宗节点的同时也把所有和(x,y)相互可达的点连到他们的祖宗节点上
//通过祖宗节点的f值，就可以知道整个并查集的大小
int dfs(int x,int y)
{
    if(p[x*n+y]!=-1)
    return find(x*n+y);
    p[x*n+y]=x*n+y;//把x，y映射成x*n+y
    f[x*n+y]=1;
    int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=0&&nx<n&&ny>=0&&ny<n&&g[x][y]!=g[nx][ny])
        {
            int tmp=dfs(nx,ny);
            Union(x*n+y,tmp);
            //把以nx,ny所在的并查集,连接到(x,y)所在的并查集上
        }
    }
    // printf("x*n+y=%d find(x*n+y)=%d\n",x*n+y,find(x*n+y));
    return find(x*n+y);
}
int main()
{
    cin>>n>>m;
    memset(p,-1,sizeof p);//初始时把所有节点的父节点都更新成-1，表示这个点还没有被访问过。
    for(int i=0;i<n;i++)
    {
        cin>>g[i];
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<f[dfs(x-1,y-1)]<<endl;
    }
    return 0;
}

不过这种方法同样会有栈溢出的风险，毕竟他只是加速了我们搜索每层的时间，但是并不能让我们的搜索层数变少。而洛谷的数据可以让并查集的方法过，而不能让dfs过，但是我在本地运行时，当数据量非常大时，dfs+并查集的方法一样会使栈溢出，所以更优的选择应该是循环+并查集或者bfs，后续会补上这两种方法。