首页 > 其他 > 详细

POJ 3984 迷宫问题

时间:2014-08-11 11:25:33      阅读:362      评论:0      收藏:0      [点我收藏+]

第二道广搜的问题

虽然思路很清晰,可真要自己把代码敲出来并不是一件容易的事

用一维数组模拟一个队列,head和tail分别记录队首和队尾

先将迷宫的起点入队,然后向四个方向拓展,如果没有出界或者没有遇到墙壁,那么入队,然后队首出队

知道搜到迷宫的出口为止

 

bubuko.com,布布扣
 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 LOCAL
28         freopen("3984in.txt", "r", stdin);
29     #endif
30 
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 }
代码君

 

POJ 3984 迷宫问题,布布扣,bubuko.com

POJ 3984 迷宫问题

原文:http://www.cnblogs.com/AOQNRMGYXLMV/p/3904075.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!