首页 > 其他 > 详细

HDU 1728 逃离迷宫

时间:2014-08-17 19:48:52      阅读:299      评论:0      收藏:0      [点我收藏+]

这道题做的我想哭啊。。WA了将近十次了吧

一开始我用数组模拟的队列,后来和老大代码对拍,感觉改的是基本都一模一样了,还是WA

实在没有办法了,改用queue了

 

题目里的x是列y是行,和代码里的反过来的,要注意!

题目里面说在起点的时候无论朝哪个方向走都不算一次转弯,所以我们将方向和转弯次数都赋值为-1,这样就不用特殊处理了

入队条件,拓展后的转弯次数小于或等于vis数组中记录的最小转弯次数即可入队

输出结果,不要一搜到终点便急着输出,应为可能后面再一次搜到终点的时候转弯次数小于k

因此可以遍历完以后再输出,或者输出yes的时候加一个限制条件:转弯次数小于等于k

两种处理方法,第二种更快一点

 

这里先把数组WA掉的代码贴上,留着以后再找错。

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;
10     int di, times;
11 }qu[20000 + 10];
12 
13 const int MAX = 200;
14 char map[105][105];
15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
16 int row, col, vis[105][105];
17 int sx, sy, ex, ey, k;
18 int head, tail;
19 
20 bool islegal(int x, int y)
21 {
22     if(x>=0 && x<row && y>=0 && y<col && map[x][y]==.)
23         return true;
24     return false;
25 }
26 
27 void BFS(void)
28 {
29     head = 0, tail = 1;
30     vis[sx][sy] = 0;
31     qu[0].x = sx, qu[0].y = sy;
32     qu[0].di = -1, qu[0].times = -1;
33     while(head < tail)
34     {
35         //if(qu[head].x==ex && qu[head].y==ey)
36             //{printf("yes\n");    return;}
37         for(int i = 0; i < 4; ++i)
38         {
39             int temp;
40             int xx = qu[head].x + dir[i][0];
41             int yy = qu[head].y + dir[i][1];
42             if(!islegal(xx, yy))    continue;
43             if(i != qu[head].di)
44                 temp = qu[head].times + 1;
45             else
46                 temp = qu[head].times;
47             if(temp > k)    continue;
48             if(temp <= vis[xx][yy])
49             {
50                 vis[xx][yy] = temp;
51                 qu[tail].x = xx, qu[tail].y = yy;
52                 qu[tail].di = i;
53                 qu[tail++].times = temp;
54             }
55         }
56         ++head;
57     }
58     if(vis[ex][ey] <= k)
59         printf("yes\n");
60     else
61         printf("no\n");
62 }
63 
64 int main(void)
65 {
66     #ifdef LOCAL
67         freopen("1728in.txt", "r", stdin);
68     #endif
69 
70     int T;
71     scanf("%d", &T);
72     while(T--)
73     {
74         scanf("%d%d", &row, &col);
75         getchar();
76         for(int i = 0; i < row; ++i)
77         {
78             for(int j = 0; j < col; ++j)
79             {
80                 scanf("%c", &map[i][j]);
81                 vis[i][j] = MAX;
82             }
83             getchar();
84         }
85         scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
86         --sx, --sy, --ex, --ey;
87         BFS();
88     }
89     return 0;
90 }
代码君

 

queue的AC代码:

bubuko.com,布布扣
 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <queue>
 6 using namespace std;
 7 
 8 struct Point
 9 {
10     int x, y;
11     int di, times;
12 }qu[20000 + 10];
13 
14 const int MAX = 200;
15 char map[105][105];
16 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
17 int row, col, vis[105][105];
18 int sx, sy, ex, ey, k;
19 
20 bool islegal(int x, int y)
21 {
22     return(x>=0 && x<row && y>=0 && y<col && map[x][y]==.);
23 }
24 
25 void BFS(void)
26 {
27     queue<Point> qu;
28     vis[sx][sy] = 0;
29     Point cur;
30     cur.x = sx, cur.y = sy;
31     cur.di = cur.times = -1;
32     qu.push(cur);
33     while(!qu.empty())
34     {
35         cur = qu.front();
36         qu.pop();
37         if(cur.x==ex&&cur.y==ey&&cur.times<=k)
38         {
39             printf("yes\n");
40             return;
41         }
42         for(int i = 0; i < 4; ++i)
43         {
44             Point next = cur;
45             next.x += dir[i][0];
46             next.y += dir[i][1];
47             if(!islegal(next.x, next.y))    continue;
48             if(i != cur.di)
49             {
50                 next.di = i;
51                 ++next.times;
52             }
53             if(next.times > k)    continue;
54             if(next.times <= vis[next.x][next.y])
55             {
56                 vis[next.x][next.y] = next.times;
57                 qu.push(next);
58             }
59         }
60     }
61     printf("no\n");
62 }
63 
64 int main(void)
65 {
66     #ifdef LOCAL
67         freopen("1728in.txt", "r", stdin);
68     #endif
69 
70     int T;
71     scanf("%d", &T);
72     while(T--)
73     {
74         scanf("%d%d", &row, &col);
75         getchar();
76         for(int i = 0; i < row; ++i)
77         {
78             for(int j = 0; j < col; ++j)
79             {
80                 scanf("%c", &map[i][j]);
81                 vis[i][j] = MAX;
82             }
83             getchar();
84         }
85         scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
86         --sx, --sy, --ex, --ey;
87         BFS();
88     }
89     return 0;
90 }
代码君

 

HDU 1728 逃离迷宫,布布扣,bubuko.com

HDU 1728 逃离迷宫

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

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