首页 > 代码库 > 1141 01迷宫
1141 01迷宫
难度：普及/提高-
题目类型：BFS
提交次数：6
涉及知识：BFS
题目描述
有一个仅由数字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 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 int a[1010][1010]; 7 int visited[1010][1010]; 8 int b[100010]; 9 int n, m, c=1;10 bool check(int x, int y){11 if(x>=1&&x<=n&&y>=1&&y<=n)12 return true;13 return false;14 }15 struct pos{16 int x;17 int y;18 pos(int xx, int yy): x(xx), y(yy){};19 };20 queue<pos>q;21 int main(){22 cin>>n>>m;23 int i, j;24 char ch[n];25 for(i = 1; i <= n; i++){26 cin>>ch;27 for(j = 0; j < n; j++)28 a[i][j+1] = ch[j] - ‘0‘;29 }30 int x, y, ans;31 while(m--){32 scanf("%d%d", &x, &y);33 if(visited[x][y]){//有记录34 printf("%d\n", b[visited[x][y]]);35 continue;36 } 37 ans = 0;38 q.push(pos(x, y));39 visited[x][y] = c;40 while(!q.empty()){41 pos temp = q.front();42 if(check(temp.x+1, y)&&!visited[temp.x+1][temp.y]&&a[temp.x][temp.y]==!a[temp.x+1][temp.y]){43 q.push(pos(temp.x+1, temp.y));44 visited[temp.x+1][temp.y] = c;45 }46 if(check(temp.x-1, y)&&!visited[temp.x-1][temp.y]&&a[temp.x][temp.y]==!a[temp.x-1][temp.y]){47 q.push(pos(temp.x-1, temp.y));48 visited[temp.x-1][temp.y] = c;49 }50 if(check(temp.x, temp.y+1)&&!visited[temp.x][temp.y+1]&&a[temp.x][temp.y]==!a[temp.x][temp.y+1]){51 q.push(pos(temp.x, temp.y+1));52 visited[temp.x][temp.y+1] = c;53 }54 if(check(temp.x, temp.y-1)&&!visited[temp.x][temp.y-1]&&a[temp.x][temp.y]==!a[temp.x][temp.y-1]){55 q.push(pos(temp.x, temp.y-1));56 visited[temp.x][temp.y-1] = c;57 }58 q.pop();59 ans++;60 }61 b[c] = ans;62 c++;63 printf("%d\n", ans);64 }65 return 0;66 }
备注：
赤裸裸的BFS，如果真的只写成赤裸裸的BFS，那就图样了……后三个点过不了。需要记忆+BFS，一条走通的路径上所有的点能到达的点数是一样的。虽然知道了要用这种方法，但在怎么记忆这个问题上耽误了特别多时间。本来用了一个vector记录走过的点，最后再把点都附上ans值，结果最后一个点还是过不去。然后想啊想啊实在没办法了，受了解析的启发。。加了一个神奇的b数组：其实bfs的时候设置一个标志量就好了（正好用visited数组记录）。。b数组记录这个标志量所对应的答案。
1141 01迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。