1141 01迷宫
题目描述
有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入输出格式
输入格式：
输入的第1行为两个正整数n，m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。
输出格式：
输出包括m行，对于每个询问输出相应答案。
输入输出样例
说明
所有格子互相可达。
对于20%的数据，n≤10；
对于40%的数据，n≤50；
对于50%的数据，m≤5；
对于60%的数据，n≤100，m≤100；
对于100%的数据，n≤1000，m≤100000。
大家看到题目可能想起了深搜的板子题：迷宫【详见“迷宫”】，但这个题目和迷宫那个题显然不是很一样，但是根据题目来看我们也自然而然能够想到深搜DFS。首先这个题基本和迷宫问题没有什么很大的区别，只是少了一个条件，多了另外一个条件：不用判断障碍物，但必须要是在0上走1，在1上走0，也就是你下一次走的和你现在走的不能一样，而且这里依然要判断重复路径和越界。
首先和迷宫一样，我们定义一个dx[4],dy[4]用来循环行走的方向，也就是下一次行走的位置，分别是：
dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}，当然也可以定义一个二维的数组b[4][2]={{1,0}{-1,0}{0,1}{0,-1}}，接下来定义一个res数组用来标记[x][y]这个点是否已经走过了，如果是，那么直接跳过，如果不是的话，再进行下一步。
下面附上代码：
#include<bits/stdc++.h>//万能头文件，但似乎会使运行变慢，因为无用库太多
using namespace std;
][];//01数组
][];//答案数组
][];//临时的坐标数组
int n, m, pl;//pl是当前区块连通的点数
][] = {{,},{,},{,-},{-,}}; //上下左右四方向的深搜
void dfs(int x, int y){
pl++;//来到一个新的点，下面存储该点坐标
lin[pl][] = x;
lin[pl][] = y;
res[x][y] = ;//这个点已经走过了，只是为了防止一趟深搜内部走重复点，所以不需要赋为pl
; i <= ; i++){
];//u,v即为目的地
];
|| u > n || v < || v > n)//超出边界？
continue;
) continue;//走到过了 ？
if(a[u][v] == a[x][y]) continue;//根据题意，并不能走？
dfs(u, v);//以上条件都不满足才向下搜索
}
}
int main(){
memset(res, , sizeof(res));//清空答案数组
scanf("%d %d", &n, &m);
; i <= n; i++)
; j <= n; j++)
scanf("%1d", &a[i][j]);//%1d，限字宽，读入方便
; i <= m; i++){
pl = ;//重置pl
int x, y;
scanf("%d %d", &x, &y);
){//已经有答案
printf("%d\n", res[x][y]);
continue;
}
dfs(x, y);
; j <= pl; j++)
res[lin[j][]][lin[j][]] = pl; //依据坐标数组，为答案数组填上pl
printf("%d\n", pl);
}
;
}