首页 > 代码库 > HDU 1242 Rescue

HDU 1242 Rescue

2024-07-17 18:02:18   235人阅读

简单变形的广搜，而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 }
代码君

 


联系
我们