链接：https://www.nowcoder.com/acm/contest/96/G 来源：牛客网
时间限制：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_back using 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; else ans = 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 solution\n"); else cout << ans << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433095.html
相关资源：JAVA上百实例源码以及开源项目