HDU 1728 逃离迷宫

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

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

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

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

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

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

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

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

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

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

 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
");    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
");
60     else
61         printf("no
");
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代码：

 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
");
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
");
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 }
代码君

对比了一下别人的代码，才知道自己写的代码有多么挫。。

http://972169909-qq-com.iteye.com/blog/1244218

这里讲了两种方法，因为题目只是问能不能在转k个弯之内到达，而不是转的最小的弯，所以DFS也是能做的。30MS多点

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int MAX = 200;
 8 char map[105][105];
 9 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
10 int row, col, vis[105][105];
11 int sx, sy, ex, ey, k;
12 bool flag; 
13 
14 bool islegal(int x, int y)
15 {
16     return(x>=0 && x<row && y>=0 && y<col && map[x][y]=='.');
17 }
18 
19 void DFS(int x, int y, int di)
20 {
21     if(x==ex && y==ey && vis[ex][ey]<=k)
22         {flag = true;   return;}
23     if(vis[x][y] > k)
24         return;
25     if(x!=ex && y!=ey && vis[x][y]==k)
26         return;
27     for(int i = 0; i < 4; ++i)
28     {
29         int tx = x + dir[i][0];
30         int ty = y + dir[i][1];
31         if(!islegal(tx, ty))
32             continue;
33         if(vis[tx][ty] < vis[x][y])
34             continue;
35         if(i!=di && vis[tx][ty] < vis[x][y]+1)
36             continue;
37         vis[tx][ty] = vis[x][y];
38         if(i != di)
39             ++vis[tx][ty];
40         DFS(tx, ty, i);
41         if(flag)
42             return;
43     }
44 }
45 
46 int main(void)
47 {
48     #ifdef LOCAL
49         freopen("1728in.txt", "r", stdin);
50     #endif
51 
52     int T;
53     scanf("%d", &T);
54     while(T--)
55     {
56         scanf("%d%d", &row, &col);
57         getchar();
58         for(int i = 0; i < row; ++i)
59         {
60             for(int j = 0; j < col; ++j)
61             {
62                 scanf("%c", &map[i][j]);
63                 vis[i][j] = MAX;
64             }
65             getchar();
66         }
67         scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
68         --sx, --sy, --ex, --ey;
69         vis[sx][sy] = -1;
70         flag = false;
71         DFS(sx, sy, -1);
72         if(flag)    printf("yes
");
73         else    printf("no
");
74     }
75     return 0;
76 }
代码君

下面重头戏来了，解法永远都是只有更好没有最好。博主讲了一个单方向优先扩展的广搜。

把一般的广搜比作一个石子在起点激起一圈圈涟漪，单方向优先的就是向开车一样“横冲直撞”、直来直往。

因为我们是要找转弯次数最小的，因此这样的搜索方式应该也能较快的找到符合条件的路径，运行时间15MS

感觉代码的有些小细节还没有理解透，等以后回过头来慢慢消化

 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 }cur, next;
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 
19 bool islegal(int x, int y)
20 {
21     return(x>=0 && x<row && y>=0 && y<col && map[x][y]=='.');
22 }
23 
24 void BFS(void)
25 {
26     queue<Point> qu;
27     vis[sx][sy] = -1;
28     Point cur;
29     cur.x = sx, cur.y = sy;
30     qu.push(cur);
31     while(!qu.empty())
32     {
33         cur = qu.front();
34         qu.pop();
35         if(cur.x==ex&&cur.y==ey&&vis[cur.x][cur.y]<=k)
36         {
37             printf("yes
");
38             return;
39         }
40         for(int i = 0; i < 4; ++i)
41         {
42             next = cur;
43             next.x += dir[i][0];
44             next.y += dir[i][1];
45             while(islegal(next.x, next.y))
46             {
47                 if(vis[next.x][next.y] < vis[cur.x][cur.y] + 1)
48                     break;
49                 vis[next.x][next.y] = vis[cur.x][cur.y] + 1;
50                 if(vis[next.x][next.y] > k)
51                     break;
52                 if(vis[next.x][next.y] == k && next.x!=ex && next.y!=ey)
53                     break;
54                 qu.push(next);
55                 next.x += dir[i][0];
56                 next.y += dir[i][1];
57             }
58         }
59     }
60     printf("no
");
61 }
62 
63 int main(void)
64 {
65     #ifdef LOCAL
66         freopen("1728in.txt", "r", stdin);
67     #endif
68 
69     int T;
70     scanf("%d", &T);
71     while(T--)
72     {
73         scanf("%d%d", &row, &col);
74         getchar();
75         for(int i = 0; i < row; ++i)
76         {
77             for(int j = 0; j < col; ++j)
78             {
79                 scanf("%c", &map[i][j]);
80                 vis[i][j] = MAX;
81             }
82             getchar();
83         }
84         scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
85         --sx, --sy, --ex, --ey;
86         BFS();
87     }
88     return 0;
89 }
代码君
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/AOQNRMGYXLMV/p/3918065.html