首页 > 代码库 > HDU 1728 逃离迷宫
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\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 else46 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 else61 printf("no\n");62 }63 64 int main(void)65 {66 #ifdef LOCAL67 freopen("1728in.txt", "r", stdin);68 #endif69 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\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 LOCAL67 freopen("1728in.txt", "r", stdin);68 #endif69 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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。