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

Description:

给你一个n*m的图，地图上’.‘代表可以走的地方，而’#'代表陷阱不能走，
'P’代表人物位置，'K’代表钥匙，'E’代表出口。人物一个，钥匙有多个，
（'K’的数量<=50)）,出口一个，每个位置可以向（上，下，左，右）四个
方向走一格，花费一个单位时间，现在你需要花费最少的时间拿到钥匙
然后从迷宫的出口出去(若没有钥匙，则不能进入迷宫出口所在的格子)。

Input:

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

Output:

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

Sample Input:

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

Sample Output:

No solution
12
No solution

题目链接

题目很明显是bfs搜索，我本来是先从起点到所有钥匙搜索一遍，然后循环每个钥匙搜索到终点，但是不知道为什么会内存超限，后来又想到钥匙到终点的搜索可以反过来搜索从终点到每个钥匙的距离。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 502;
const double eps = 1e-5;
const double e = 2.718281828459;

struct ac {
    int x, y, step;
};

int t;
int n, m;
int st_i, st_j;
int key_cnt;
int bfs_key_cnt;
int en_i, en_j;
int ans;
char maze[maxn][maxn];
int dis_p[maxn][maxn];
int dis_e[maxn][maxn];
bool vis[maxn][maxn];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

void bfs(int x, int y) {
    mem(vis, 0);
    bfs_key_cnt = 0;
    queue<ac> que;
    ac push_;
    push_.x = x;
    push_.y = y;
    push_.step = 0;
    que.push(push_);
    while (!que.empty()) {
        ac keep = que.front();
        que.pop();
        if (maze[keep.x][keep.y] == 'K') {
            if (x == st_i && y == st_j) {
                dis_p[keep.x][keep.y] += keep.step;
            }
            else if (x == en_i && y == en_j) {
                dis_e[keep.x][keep.y] += keep.step;
            }
            bfs_key_cnt++;
            if (bfs_key_cnt == key_cnt) {
                return;
            }
        }
        for (int i = 0; i < 4; ++i) {
            int nx = keep.x + dx[i], ny = keep.y + dy[i];
            if (!vis[nx][ny] && nx > 0 && nx <= n && ny > 0 && ny <= m && maze[nx][ny] != '#' && maze[nx][ny] != 'E') {
                vis[nx][ny] = 1;
                ac _push;
                _push.x = nx;
                _push.y = ny;
                _push.step = keep.step + 1;
                que.push(_push);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--) {
        mem(dis_p, 0);
        mem(dis_e, 0);
        ans = INF;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> maze[i][j];
                if (maze[i][j] == 'P') {
                    st_i = i;
                    st_j = j;
                }
                else if (maze[i][j] == 'K') {
                    key_cnt++;
                }
                else if (maze[i][j] == 'E') {
                    en_i = i;
                    en_j = j;
                }
            }
        }
        bfs(st_i, st_j);
        bfs(en_i, en_j);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (dis_p[i][j] + dis_e[i][j] < ans && dis_p[i][j] != 0 && dis_e[i][j] != 0) {
                    ans = dis_p[i][j] + dis_e[i][j];
                }
            }
        }
        if (ans != INF) {
            cout << ans << endl;
        }
        else {
            cout << "No solution" << endl;
        }
    }
    return 0;
}