首页 > 代码库 > HDU 1242 Rescue
HDU 1242 Rescue
简单变形的广搜,而HDU 1026 Ignatius and the Princess I 是这道题的升级版,因为每个格子停留的时间可能不相同。
这里,天使的朋友可能有多个,所以我们从天使开始逆向去找他的朋友,最先找到他的朋友就是最短时间。
题目的变形在于多了守卫,每当一个守卫进入队列,第一次只扩展当前位置,仅仅是时间加1,第二次再向四个方向扩展。
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 steps;12 }start;13 14 int row, col;15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};16 int vis[205][205];17 char map[205][205];18 19 void BFS(void)20 {21 queue<Point> qu;22 start.steps = 0;23 qu.push(start);24 while(!qu.empty())25 {26 Point fir = qu.front();27 if(map[fir.x][fir.y] == ‘r‘)28 {29 printf("%d\n", fir.steps);30 return;31 }32 if(map[fir.x][fir.y] == ‘x‘)33 {//第一次停留在原地34 Point next;35 next.x = fir.x, next.y = fir.y, next.steps = fir.steps + 1;36 map[fir.x][fir.y] = ‘.‘;//记得改变‘x‘,下一次变开始向四周扩展37 qu.push(next);38 qu.pop();39 continue;40 }41 for(int i = 0; i < 4; ++i)42 {43 int xx = fir.x + dir[i][0];44 int yy = fir.y + dir[i][1];45 if(xx<0 || xx>=row || yy<0 || yy>=col || vis[xx][yy] || map[xx][yy]==‘#‘)46 continue;47 else48 {49 Point next;50 next.x = xx, next.y = yy, next.steps = fir.steps + 1;51 vis[xx][yy] = 1;52 qu.push(next);53 }54 }55 qu.pop();56 }57 printf("Poor ANGEL has to stay in the prison all his life.\n");58 }59 60 int main(void)61 {62 #ifdef LOCAL63 freopen("1242in.txt", "r", stdin);64 #endif65 66 while(scanf("%d%d", &row, &col) == 2)67 {68 getchar();69 for(int i = 0; i < row; ++i)70 {71 for(int j = 0; j < col; ++j)72 {73 scanf("%c", &map[i][j]);74 if(map[i][j] == ‘a‘)75 start.x = i, start.y = j;76 }77 getchar();78 }79 80 memset(vis, 0, sizeof(vis));81 map[start.x][start.y] = ‘#‘;82 vis[start.x][start.y] = 1;83 BFS();84 }85 return 0;86 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。