第一届程序设计竞赛题解（I题）

第一届程序设计竞赛题解（I题）

I.从你的全世界路过

题目描述：

在电影中，陈末与幺鸡约定了要在稻城再见。
但是，陈末在快抵达稻城的时候，被一群可恶的神秘人抓走了，神秘人把陈末关在了一个没有出口的二维迷宫里。
上帝见陈末如此可怜，就给了陈末一张迷宫的地图，并告诉给陈末，只要陈末能到达迷宫的边界，上帝就会花 1 单位时间帮他逃出迷宫。

迷宫内有毒气，毒气在每个单位时间会向四周扩散（即向四个方向扩散一个单位），毒气无法扩散到墙上。
例如，毒气此时在 (x, y)，那么毒气会花 1 个单位时间扩散到 (x, y+1), (x+1, y), (x-1, y), (x, y-1)，并在新的位置再次扩散，前提为目标点不是墙，且不在迷宫范围之外。

陈末在每个单位时间只能向一个方向前进一个单位，陈末翻不了这里的墙。
例如，陈末此时在 (x, y)，那么陈末可以花费 1 个单位时间走到 (x, y+1), (x+1, y), (x-1, y), (x, y-1) 中的任意一个，前提为目标点不是墙，且不在迷宫范围之外。

请问，陈末至少要花多少时间才能逃出迷宫，如果陈末始终无法逃出迷宫请输出 “NO” （不包含双引号）

输入描述：

第一行两个整数 n (1 ≤ n ≤ 10³)，m(1 ≤ m ≤ 10 ³)，分别表示二维迷宫的行数和列数。
下面有 n 行 ，每行 m 个字符，代表二维迷宫的地图。
* 代表这个位置有毒气
# 代表这个位置有墙
. 代表这个位置是空地
C 代表陈末在这个位置
保证地图只有以上4种字符，并且C保证只出现1次。
注意：不保证毒气只有一个位置具有。

输出描述：

陈末至少要花多少时间才能逃出迷宫，如果陈末始终无法逃出迷宫请输出 “NO” （不包含双引号）

示例：

输入：
3 3
*##
*C.
###
输出：
2
说明：
陈末可以花费1单位时间从 (2, 2) 到达 (2, 3)，然后上帝就会花1个单位时间救他。

思路：
双重最短路问题，可以使用两个 BFS 来求解，利用队列实现，分别求出毒气到达某点的最短时间和陈末到达某点的最短时间。特别要注意，毒气不止一个地方有，每次遍历都需要查找毒气的位置；而陈末的位置只有一个，找到后即可标记下来。
每次比较时间，若毒气到达该点的时间大于陈末到达的时间，则陈末可以赶在毒气到达前走到该点，再循环看下一个点，一直到出口。若毒气到达该点的时间小于陈末的时间，则在陈末到该点之前，就已经布满毒气，再走，则陈末卒。

AC代码如下：

#include <bits/stdc++.h>
#define PII pair<int, int>
#define ll long long
using namespace std;const int INF = 0x3f3f3f3f;
const int N = 1e3 + 5;int n, m;
char mp[N][N];//地图数组
int a[N][N];//毒气到达该点的时间
int b[N][N];//陈末到达该点的时间
int sx, sy;//陈末的起点位置
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};//方向数组
int ans;//陈末走出迷宫时间struct node{int x;int y;int t;//时间
};queue<PII> ta;//存放毒气的队列
queue<node> tb;//存在陈末的队列//这里我将两个 bfs 放在一块写了
void bfs()
{while (!ta.empty()){//申请名为 u 的保存两个整数的pair容器PII u = ta.front();//取出队首元素放入pair容器中ta.pop();//删除队首元素for (int i = 0; i < 4; i++){//下一个点的坐标int xx = u.first + dx[i], yy = u.second + dy[i];//判断边界和墙壁if (xx < 1 || yy < 1 || xx > n || yy > m || mp[xx][yy] == '#')continue;//不更新已经走过的位置if (a[xx][yy] <= a[u.first][u.second] + 1)continue;//拓展后，符合条件的点放入队尾ta.push({xx, yy});//毒气到达该点的最短时间a[xx][yy] = min(a[xx][yy], a[u.first][u.second] + 1);}}//陈末的队列放入陈末的起点，时间初始化为0tb.push({sx, sy, 0});b[sx][sy] = 0;ans = -1;while (!tb.empty()){//取出队首元素放入结构体中node v = tb.front();//用完删除队首元素tb.pop();//如果走到了边界if (v.x == 1 || v.y == 1 || v.x == n || v.y == m ){//且下一步时，人到达的时间小于毒气到达的时间if (a[v.x][v.y] >= v.t + 1){//将时间加一ans = v.t + 1;break;}}//遍历下一个点for (int i = 0; i < 4; i++){int xx = v.x + dx[i], yy = v.y + dy[i];if (xx < 1 || yy < 1 || xx > n || yy > m)continue;if (b[xx][yy] <= v.t + 1)continue;//如果没有毒气，且人到达的时间小于毒气到达的时间，放入队尾if (mp[xx][yy] == '.' && v.t + 1 <= a[xx][yy]){tb.push({xx, yy, v.t + 1});//时间加一b[xx][yy] = v.t + 1;}}}}int main()
{scanf("%d %dn", &n, &m);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> mp[i][j];//将时间初始化尽量大a[i][j] = b[i][j] = INF;//找到陈末的起点if (mp[i][j] == 'C'){sx = i;sy = j;}//找到毒气的位置，放入队列中，标记if (mp[i][j] == '*'){ta.push({i, j});//初始化时间为0a[i][j] = 0;}}}//调用BFS遍历bfs();if (ans == -1)puts("NO");elseprintf("%dn", ans);return 0;
}