这道题可以用DFS,也可以用BFS,这里我采用了DFS(因为懒)。

题目大意

给定一个只含0011n×nn \times n的迷宫:

1
2
3
4
5
n=4
1 0 0 1
1 1 0 0
0 1 1 0
1 0 0 1

从每一个为00的位置,可以走到相邻的11处;从每一个为11的位置,可以走到相邻的00处。即上一个走过来的格子不能与现在的格子相同。

接下来有mm次查询,每次查询给定一个x,yx,y,表示迷宫里第xx行第yy列的格子,询问从这里开始最多能走到几个格子(包括自身)。

做法

普通DFS

根据题意,很容易得到第一版的DFS代码:

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
#include<bits/stdc++.h>
using namespace std;
bool Map[1005][1005];
int mapBooker[1005][1005];
int n,m;
int search(int x,int y,bool last){
/*判定是否越界、已经搜索过*/
if(last==Map[x][y] or x<1 or x>n or y<1 or y>n or !mapBooker[x][y])return 0;
mapBooker[x][y]=1;//标记
return search(x-1,y,id,Map[x][y])+search(x+1,y,id,Map[x][y])+search(x,y+1,id,Map[x][y])+search(x,y-1,id,Map[x][y])+1;//继续搜索,搜索周围四个点,同时算上自己

}
int main(){
char tmp;
std::ios::sync_with_stdio(false);
cin.tie(0);//加快cin的读入
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>tmp;
Map[i][j]=(tmp=='0'?false:true);
}
}
int x,y;
for(int i=1;i<=m;i++){
memset(mapBooker,0,sizeof(mapBooker));//清空标记数组
cin>>x>>y;
cout<<search(x,y,!Map[x][y])<<endl;
}
}

但这样的代码只拿了70分,剩下的三个点全部超时。
image.png

DFS+联通块

我们可以发现,在同一个块里的点都能相互联通,所以,只要这一个块里的其中一个点被搜过了,其它的点其实已经得出来了:
image.png
在上图,红框框起来的点都可以互相到达,所以他们最多能走到的格子都一样,即这个联通块内的坐标个数——77个。

这样,可以得出第二版代码:

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
#include<bits/stdc++.h>
using namespace std;
bool Map[1005][1005];
int mapBooker[1005][1005];
int answerQueue[100005];
int n,m;
int search(int x,int y,int id,bool last){
/*判定是否越界、已经搜索过*/
if(last==Map[x][y] or x<1 or x>n or y<1 or y>n or mapBooker[x][y]!=-1)return 0;
mapBooker[x][y]=id;//标记联通块编号
return answerQueue[id]=search(x-1,y,id,Map[x][y])+search(x+1,y,id,Map[x][y])+search(x,y+1,id,Map[x][y])+search(x,y-1,id,Map[x][y])+1;//搜索,同时将答案放入答案区

}
int main(){
char tmp;
std::ios::sync_with_stdio(false);
cin.tie(0);
memset(mapBooker,-1,sizeof(mapBooker));
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>tmp;
Map[i][j]=(tmp=='0'?false:true);
}
}
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
if(mapBooker[x][y]!=-1){//已经被搜过了
cout<<answerQueue[mapBooker[x][y]]<<endl;
}
else cout<<search(x,y,i,!Map[x][y])<<endl;
}
}

由于联通块的特性,我们不需要每次都清空mapBooker数组,因为只要搜过的地方就没必要再搜了。

再次提交,成功AC。
image.png