首页 > 代码库 > POJ 3984 迷宫问题
POJ 3984 迷宫问题
第二道广搜的问题
虽然思路很清晰,可真要自己把代码敲出来并不是一件容易的事
用一维数组模拟一个队列,head和tail分别记录队首和队尾
先将迷宫的起点入队,然后向四个方向拓展,如果没有出界或者没有遇到墙壁,那么入队,然后队首出队
知道搜到迷宫的出口为止
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 struct Point 8 { 9 int x, y, pre;10 }queue[30];11 12 int map[7][7];13 int head = 0, tail = 1;14 int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};15 16 void output(int i)17 {18 if(queue[i].pre != -1)19 {20 output(queue[i].pre);21 printf("(%d, %d)\n", queue[i].x, queue[i].y);22 }23 }24 25 int main(void)26 {27 #ifdef LOCAL28 freopen("3984in.txt", "r", stdin);29 #endif30 31 for(int i = 0; i < 5; ++i)32 for(int j = 0; j < 5; ++j)33 scanf("%d", &map[i][j]);34 //将迷宫的起点入队35 queue[0].x = queue[0].y = 0;36 queue[0].pre = -1;37 map[0][0] = 1;38 printf("(0, 0)\n");39 while(head < tail)40 {41 for(int i = 0; i < 4; ++i)42 {43 int xx = queue[head].x + dir[i][0];44 int yy = queue[head].y + dir[i][1];45 if(xx<0 || xx >=5 || yy<0 || yy>=5 || map[xx][yy])46 continue;47 map[xx][yy] = 1; //标记已经走过48 queue[tail].x = xx;49 queue[tail].y = yy;50 queue[tail++].pre = head;51 if(xx == 4 && yy == 4)52 output(head);//找到要搜索的目标,开始输出53 }54 ++head;//队首元素出队55 }56 printf("(4, 4)\n");57 return 0;58 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。