P6742 水题求调 玄关

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef int LL;
const LL N = 1010, M = 1000010;
LL n, m, s, t;
LL dx[5] = {0, 1, 0, -1, 0}, dy[5] = {0, 0, 1, 0, -1};
struct nod{
    LL x, y;
    inline friend bool operator <(const nod &x, const nod &y) {
        return x.y > y.y;
    }
};

LL b[N][N], d[N][N], dis[M], vis[M];
vector<pair<LL, LL>> a[M];
priority_queue<nod> q;
int main() {
    memset(d, 0x3f, sizeof(d));
    memset(dis, 0x3f, sizeof(dis));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        getchar();
        for (int j = 1; j <= m; j++) {
            char c;
            c = getchar();
            if (c == '.') b[i][j] = 0;
            if (c == '#') b[i][j] = 1;
            if (c == 'S') {
                b[i][j] = 0;
                s = i * m + j;
            }

            if (c == 'C') {
                b[i][j] = 0;
                t = i * m + j;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (b[i][j]) continue;
            for (int k = 1; k <= 4; k++) {
                LL nx = i + dx[k];
                LL ny = j + dy[k];
                if (nx <= 0 || nx >= n + 1 || ny <= 0 || ny >= m + 1 || b[nx][ny]) continue;
                LL nz = nx * m + ny;
                LL z = i * m + j;
                a[z].push_back({nz, 1});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        LL tmp = -1;
        for (int j = 1; j <= m; j++) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = j;
            d[i][j] = min(d[i][j], j - tmp + 1);
        }
    }

    for (int i = 1; i <= n; i++) {
        LL tmp = -1;    
        for (int j = m; j >= 1; j--) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = j;
            d[i][j] = min(d[i][j], tmp - j + 1);
        }        
    }

    for (int j = 1; j <= m; j++) {
        LL tmp = -1;
        for (int i = 1; i <= n; i++) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = i;
            d[i][j] = min(d[i][j], i - tmp + 1);
        }
    }   

    for (int j = 1; j <= m; j++) {
        LL tmp = -1;
        for (int i = n; i >= 1; i--) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = i;
            d[i][j] = min(d[i][j], tmp - i + 1);
        }
    }    
    
    for (int i = 1; i <= n; i++) {
        LL tmp = -1;
        for (int j = 1; j <= m; j++) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = j;
            a[i * m + j].push_back({i * m + tmp, min(d[i][j], j - tmp)});
        }
    }

    for (int i = 1; i <= n; i++) {
        LL tmp = -1;    
        for (int j = m; j >= 1; j--) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = j;
            a[i * m + j].push_back({i * m + tmp, min(d[i][j], tmp - j)});
        }        
    }

    for (int j = 1; j <= m; j++) {
        LL tmp = -1;
        for (int i = 1; i <= n; i++) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = i;
            a[i * m + j].push_back({tmp * m + j, min(d[i][j], i - tmp)});
        }
    }   

    for (int j = 1; j <= m; j++) {
        LL tmp = -1;
        for (int i = n; i >= 1; i--) {
            if (b[i][j]) { tmp = -1; continue; }
            if (tmp == -1) tmp = i;
            a[i * m + j].push_back({tmp * m + j, min(d[i][j], tmp - i)});
        }
    }    

    dis[s] = 0;
    q.push({s, dis[s]});
    while (q.size()) {
        nod prz = q.top();
        q.pop();
        if (vis[prz.x]) continue;
        vis[prz.x] = 1;
        for (pair<LL, LL> tmp : a[prz.x]) {
            if (vis[tmp.first]) continue;
            if (dis[tmp.first] > dis[prz.x] + tmp.second) {
                dis[tmp.first] = dis[prz.x] + tmp.second;
                q.push({tmp.first, dis[tmp.first]});
            }
        }
    }

    printf("%d\n", dis[t]);
}