P8693 [蓝桥杯 2019 国 AC] 大胖子走迷宫 参考代码

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'

typedef long long LL;
const int maxn = 300 + 100;
const int INF = 0x3f3f3f3f;
struct Node {
    int x, y, a, dis;
    Node() {}
    Node(int x, int y, int a, int dis) : x(x), y(y), a(a), dis(dis) {}
};

bool operator<(const Node &a, const Node &b) {
    return a.dis > b.dis;
}

int n, k, ans;
char str[maxn][maxn];
int dis[maxn][maxn][3];
bool vis[maxn][maxn][3];
priority_queue<Node> que;
const int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

bool canGo(int x, int y, int a) {
    for (int i = -a; i <= a; ++i) {
        for (int j = -a; j <= a; ++j) {
            int xx = x + i;
            int yy = y + j;
            if (!in(xx, yy) || str[xx][yy] == '*') {
                return false;
            }
        }
    }
    return true;
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> str[i];
    }
    memset(dis, 0x3f, sizeof(dis));
    que.push(Node(2, 2, 2, 0));
    dis[2][2][2] = 0;
    while (!que.empty()) {
        Node tmp = que.top();
        que.pop();
        if (vis[tmp.x][tmp.y][tmp.a]) {
            continue;
        }
        vis[tmp.x][tmp.y][tmp.a] = true;
        for (int i = 0; i < 4; ++i) {
            int x = tmp.x + dir[i][0];
            int y = tmp.y + dir[i][1];
            if (!in(x, y) || str[x][y] == '*') {
                continue;
            }
            for (int a = tmp.a; a >= 0; --a) {
                if (!canGo(x, y, a)) {
                    continue;
                }
                int d = max(tmp.dis + 1, (2 - a) * k + 1);
                if (d < dis[x][y][a]) {
                    dis[x][y][a] = d;
                    que.push(Node(x, y, a, d));
                }
            }
        }
    }
    ans = INF;
    for (int i = 0; i < 3; ++i) {
        ans = min(ans, dis[n - 3][n - 3][i]);
    }
    cout << ans << endl;

    return 0;
}