题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入输出格式
输入格式： 输入的第1行为两个正整数n，m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
输出格式： 输出包括m行，对于每个询问输出相应答案。
输入输出样例
输入样例#1： 2 2 01 10 1 1 2 2 输出样例#1： 4 4
说明
所有格子互相可达。
对于20%的数据，n≤10；
对于40%的数据，n≤50；
对于50%的数据，m≤5；
对于60%的数据，n≤100，m≤100；
对于100%的数据，n≤1000，m≤100000。
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=
1000+
50;
int n,m,total,t,p[MAXN*MAXN];
int v[MAXN][MAXN],f[MAXN][MAXN];
int dr[
4][
2]={{
1,
0},{
0,-
1},{-
1,
0},{
0,
1}};
bool judge(
int x,
int y)
{
if(x<=
0||y<=
0||x>n||y>n)
return false;
return true;
}
void dfs(
int x,
int y,
int tot)
{
f[x][y]=tot;
total++;
for(
int i=
0;i<
4;i++)
{
int nx=x+dr[i][
0],ny=y+dr[i][
1];
if(judge(nx,ny)&&v[nx][ny]!=v[x][y]&&f[x][y]!=f[nx][ny])dfs(nx,ny,tot);
}
}
int search(
int x,
int y)
{
total=
0;
dfs(x,y,++t);
p[t]=total;
return total;
}
int main(){
cin>>n>>m;
for(
int i=
1;i<=n;i++)
{
for(
int j=
1;j<=n;j++)
{
char a=getchar();
while(a!=
'0'&&a!=
'1')a=getchar();
if(a==
'0')v[i][j]=
0;
else if(a==
'1')v[i][j]=
1;
}
}
for(
int i=
1;i<=m;i++)
{
int x,y,ans;
cin>>x>>y;
if(f[x][y])ans=p[f[x][y]];
else ans=search(x,y);
cout<<ans<<endl;
}
return 0;
}
