记录编号	569976	评测结果	AAAAAAAAAA
题目名称	穿越栅栏	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-03-20 13:35:14	内存使用	0.00 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <queue>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define MAX(_a, _b) [&](int __a, int __b) { return __a < __b ? __b : __a; }((_a), (_b))
#define MIN(_a, _b) [&](int __a, int __b) { return __a > __b ? __b : __a; }((_a), (_b))
#define ABS(_x) [&](int __x) { return __x < 0 ? -__x : __x; }(_x)
#define fi first
#define se second 
#define INF 0x3f3f3f3f
 
using ll = long long;
using PII = std::pair<int, int>;
 
namespace IO {
    template <typename T> inline T read() {
        char ch = getchar();
        T ret = 0, sig = 1;
        while(ch < '0' || ch > '9') { if(ch == '-') sig = -1; ch = getchar(); }
        while(ch >= '0' && ch <= '9') ret *= 10, ret += ch - 48, ch = getchar();
        return ret * sig;
    }
    template <typename T> inline void write(T out) {
        if(!out) { putchar('0'), putchar(' '); return; }
        int stk[100], tt = 0;
        if(out < 0) out = -out, putchar('-');
        while(out) stk[tt++] = out % 10, out /= 10;
        for(register int i = --tt; i>=0; --i) putchar(stk[i] + 48);
        putchar(' ');
    }
    template <typename T> inline void read(T& ret) { ret = IO::read<T>(); }
    template <typename T, typename... Args> inline void read(T& x, Args&... args) { IO::read(x), IO::read(args...); }
    template <typename T, typename... Args> inline void write(T x, Args... args)  { IO::write(x), IO::write(args...); }
};
 
 
const int N = 210;
char g[N][N];
int dist[N][N];
bool st[N][N];
int n, m, res, cnt;
std::string s;
 
PII expt[4]; // export
 
int dx[] = { 0, 2, 0, -2 }, dy[] = { 2, 0, -2, 0 };
 
struct Node { int x, y, w; };
 
inline bool is_valid(PII x) { return x.fi >= 1 && x.fi <= n && x.se >= 1 && x.se <= m; }
 
inline void bfs(int id) {
    memset(st, 0, sizeof st);
 
    std::queue<Node> q;
    st[expt[id].fi][expt[id].se] = true;
    q.push((Node) { expt[id].fi, expt[id].se, 0 });
 
    while(q.size()) {
        Node t = q.front(); q.pop();
        int x = t.x, y = t.y, w = t.w;
        dist[x][y] = MIN(dist[x][y], w);
        for (register int i = 0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            int mx = x + dx[i] / 2, my = y + dy[i] / 2;
            if((PII) { x, y } != expt[id]) {
                if(is_valid({nx, ny}))
                    if (!st[nx][ny] && g[nx][ny] == ' ' && g[mx][my] == ' ') {
                        q.push((Node) { nx, ny, w + 1 });
                        st[nx][ny] = true;
                    }
            } else {
                if(is_valid({mx, my}))
                    if (!st[mx][my] && g[mx][my] == ' ') {
                        q.push((Node) { mx, my, w + 1 });
                        st[mx][my] = true;
                    }
            }
        }
    }
}
 
int main() {
    #ifdef DEBUG
    OPEN(test);
    #endif
    OPEN(maze1);
    IO::read(m, n);
    n = 2 * n + 1, m = 2 * m + 1;
 
    memset(dist, 0x3f, sizeof dist);
 
    for (register int i = 1; i<=n; ++i) {
        std::getline(std::cin, s);
        memcpy(g[i]+1, s.c_str(), m);
        for (register int j = 1; j<=m; ++j) {
            if (i == 1 || j == 1 || i == n || j == m)
                if(g[i][j] == ' ') expt[++cnt] = { i, j };
        }
    }
 
    bfs(1), bfs(2);
 
    for (register int i = 1; i<=n; ++i) 
        for (register int j = 1; j<=m; ++j) 
            if (dist[i][j] != INF) res = MAX(res, dist[i][j]);
 
    IO::write(res);
    return 0;
}