我用测试点给的数据来测试然后和答案对比发现一模一样,这为什么wa了???
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 10;
int vis[MAXN][MAXN];//迷宫地图
bool is_vis[MAXN][MAXN]; //标记是否走过
int n, m;//n * n矩阵 m个问题
struct pos{
int x;
int y;
};
pos Div[4] = {{1 , 0}, {-1, 0}, {0, 1}, {0, -1}};//代表的前后左右移动
bool check(pos begin, pos Next){//检查有无越界已经能否移动(题目要求vis不同可以移动)
if(Next.x > 0 && Next.x <= n && Next.y > 0 && Next.y <= n)
return ((vis[begin.x][begin.y] != vis[Next.x][Next.y]) && (!is_vis[Next.x][Next.y]));
else
return false;
}
int BFS(pos begin){
int cnt = 1;//起点也算一点
queue<pos> q;
q.push(begin);
is_vis[begin.x][begin.y] = true;
pos One, Next;
while(!q.empty()){
One = q.front();
q.pop();
for(int i = 0; i < 4; i++){//前后左右四种选择
Next.x = One.x + Div[i].x;
Next.y = One.y + Div[i].y;
if(check(One, Next)){
//cout << Next.x << " " << Next.y << endl;
q.push(Next);
is_vis[Next.x][Next.y] = true;
cnt++;
}
}
}
return cnt;
}
int main(){
char c;
scanf("%d %d", &n, &m);
getchar();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
c = getchar();
vis[i][j] = c - '0';
}
getchar();
}
for(int i = 1; i <= m; i++){
pos start;
scanf("%d %d",&start.x, &start.y);
memset(is_vis, false, sizeof(is_vis));
printf("%d\n", BFS(start));
}
return 0;
}