最短路SPFA

作为第一篇最短路题解,我感觉这貌似是最简单的一个思路。

我们首先把整个字符矩阵读到字符二维数组中

建图

  • 对于$ch_{x,y}$,如果$x mod 2 == 0$且$y mod 2 == 0$,暂且管这样的一格叫做房间
  • 对于每一个房间,如果它四面有一个墙壁是空格,那么向它通向的那个房间建边

思路

扫一遍边缘找到两个开口,以它们为起点跑SPFA,对于每个节点的结果取这两次的较小值,最终答案为所有房间节点的距离最大值$+1$

注意事项

本题读入毒瘤,每行需要两个getchar()过滤回车

代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 205;
const int INF = 0x3f3f3f3f;
const int DX[4] = {-2, 0, 2, 0};
const int DY[4] = {0, -2, 0, 2};
const int BX[4] = {-1, 0, 1, 0};
const int BY[4] = {0, -1, 0, 1};

char mp[MAXN][MAXN];
int dis[MAXN * MAXN];
int w, h, n, m, cnt = -1;
int s[MAXN * 4];
int res[3][MAXN * MAXN];
bool vis[MAXN * MAXN];

struct Edge{
    int to, val;
    Edge *next;
    Edge(int to, int val, Edge *next): to(to), val(val), next(next){}
};

Edge *head[MAXN * MAXN];

void AddEdge(int u, int v, int w) {
    head[u] = new Edge(v, w, head[u]);
}

int Id(int x, int y) {
    return m * (x - 1) + y;
}

void Spfa(int s) {
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    queue<int> q; q.push(s); vis[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = false;
        for (Edge *e = head[u]; e; e = e->next) {
            int v = e->to;
            if (dis[v] > dis[u] + e->val) {
                dis[v] = dis[u] + e->val;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    cin >> w >> h;
    n = h * 2 + 1; m = w * 2 + 1;
    /*getchar();
    for (int i = 1; i <= n; i++) {
        int cnt = 0; char ch;
        while (ch = getchar(), ch != '\n') mp[i][++cnt] = ch;
    }*/
    for (int i = 1; i <= n; i++) {
        getchar();
        for (int j = 1; j <= m; j++) {
            mp[i][j] = getchar();
            if (mp[i][j] == '\n') mp[i][j] = getchar();
        }
    }
    for (int i = 2; i < n; i += 2) {
        for (int j = 2; j < m; j += 2) {
            for (int k = 0; k < 4; k++) {
                int x = i + DX[k], y = j + DY[k], bx = i + BX[k], by = j + BY[k];
                if (x < 1 || x > n || y < 1 || y > m || mp[bx][by] != ' ') continue;
                AddEdge(Id(i, j), Id(x, y), 1);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        if (mp[1][i] == ' ') s[++cnt] = Id(2, i);
        if (mp[n][i] == ' ') s[++cnt] = Id(n - 1, i);
    }
    for (int i = 1; i <= n; i++) {
        if (mp[i][1] == ' ') s[++cnt] = Id(i, 2);
        if (mp[i][m] == ' ') s[++cnt] = Id(i, m - 1);
    }
    Spfa(s[0]);
    for (int i = 1; i <= n * m; i++) res[0][i] = dis[i];
    Spfa(s[1]);
    for (int i = 1; i <= n * m; i++) res[1][i] = dis[i];
    for (int i = 1; i <= n * m; i++) res[2][i] = min(res[1][i], res[0][i]);
    int ans = 0;
    for (int i = 1; i <= n * m; i++) {
        if (res[2][i] < INF) ans = max(ans, res[2][i]);
    }
    cout << ans + 1 << endl;
    return 0;