2018年长沙理工大学第十三届程序设计竞赛 G 逃离迷宫 【BFS】

2018年长沙理工大学第十三届程序设计竞赛 G 逃离迷宫 【BFS】

链接：
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
给你一个n*m的图，地图上’.’代表可以走的地方，而’#’代表陷阱不能走，
‘P’代表人物位置，’K’代表钥匙，’E’代表出口。人物一个，钥匙有多个，
（’K’的数量<=50)）,出口一个，每个位置可以向（上，下，左，右）四个
方向走一格，花费一个单位时间，现在你需要花费最少的时间拿到钥匙
然后从迷宫的出口出去(若没有钥匙，则不能进入迷宫出口所在的格子)。
输入描述:

第一行一个整数T(T <= 50)，代表数据的组数
接下来一行n,m(n<=500,m<=500),代表地图的行和列
接下来n行，每行一个长度为m的字符串，组成一个图。

输出描述:

如果可以出去，输出所花费的最少时间。
如果不能出去，输出一行”No solution”。

示例1
输入

3
5 5
....P
##..E
K#...
##...
.....
5 5
P....
.....
..E..
.....
....K
5 5
P#..E
.#.#.
.#.#.
.#.#.
...#K

输出

No solution
12
No solution

思路
两次BFS

第一次BFS 求 入口 到每个钥匙的最短步数 存下来

第二次BFS 求 出口 到每个钥匙的最短步数 存下来

如果 钥匙存在的地方 到入口和到出口都可行 那么 这个答案就是可行的

找出 所有可行的答案 去最小值

AC代码

#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <numeric> 
#include <sstream>
#include <iomanip>
#include <limits>#define CLR(a, b) memset(a, (b), sizeof(a))
#define pb push_backusing namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;const double PI = acos(-1.0);
const double E = exp(1.0);
const double eps = 1e-8;const int INF = 0x3f3f3f3f;
const int maxn = 5e2 + 5;
const int MOD = 1e9;int G[maxn][maxn];    // K 2 
int v[maxn][maxn];
int k[maxn][maxn];int px, py, ex, ey;int ans;int n, m;int Move[4][2] =
{-1, 0,1, 0,0,-1,0, 1,
};struct node
{int x, y, step;
};bool ok(int x, int y)
{if (x < 0 || x >= n || y < 0 || y >= m || G[x][y] == 0 || v[x][y])return false;return true;
}void bfs(int x, int y, int flag)
{CLR(v, 0);queue <node> q;node tmp;tmp.x = x;tmp.y = y;tmp.step = 0;q.push(tmp);v[tmp.x][tmp.y] = 1;while (!q.empty()){node u = q.front(), w;q.pop();if (G[u.x][u.y] == 2){if (flag){if (k[u.x][u.y] == -1)return;elseans = min(ans, k[u.x][u.y] + u.step);}else{k[u.x][u.y] = u.step;}}for (int i = 0; i < 4; i++){w.x = u.x + Move[i][0];w.y = u.y + Move[i][1];w.step = u.step + 1;if (ok(w.x, w.y)){q.push(w);v[w.x][w.y] = 1;}}}
}int main()
{int t;cin >> t;while (t--){scanf("%d%d", &n, &m);char c;CLR(k, -1);for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){scanf(" %c", &c);if (c == '#')G[i][j] = 0;else{G[i][j] = 1;if (c == 'P')px = i, py = j;else if (c == 'E')ex = i, ey = j;else if (c == 'K')G[i][j] = 2;}}}ans = INF;G[ex][ey] = 0;bfs(px, py, 0);G[ex][ey] = 1;bfs(ex, ey, 1);if (ans == INF)printf("No solutionn");elsecout << ans << endl;}
}

转载于:.html