Submission #1217413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217413		i_love_spring	Portals (BOI14_portals)	C++20	0 / 100	7 ms	16340 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define int long long
const int N = 1005, inf = 1e9 + 5;
const int rc[]{0, 0, 1, -1};
const int cc[]{1, -1, 0, 0};
int n, m, sx, sy, cx, cy, d[N][N], dw[N][N];
ar<int, 2> rht[N][N], lft[N][N], down[N][N], up[N][N];
char a[N][N];
bool valid(int x, int y) {
    return (x > 0 && y > 0 && x <= n && y <= m);
}
void comp() {
    for (int i = 1; i <= n; i++) {
        int x = -1, y = -1;
        for (int j = m; j > 0; j--) {
            if (a[i][j] == '#') x = y = -1;
            else if (x == -1) x = i, y = j;
            rht[i][j] = {x, y};
        }
        x = y = -1;
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '#') x = y = -1;
            else if (x == -1) x = i, y = j;
            lft[i][j] = {x, y};
        }
    }
    for (int j = 1; j <= m; j++) {
        int x = -1, y = -1;
        for (int i = n; i > 0; i--) {
            if (a[i][j] == '#') x = y = -1;
            else if (x == -1) x = i, y = j;
            down[i][j] = {x, y};
        }
        x = y = -1;
        for (int i = 1; i <= n; i++) {
            if (a[i][j] == '#') x = y = -1;
            else if (x == -1) x = i, y = j;
            up[i][j] = {x, y};
        }
    }
}
void bfs() {
    queue<ar<int, 2>> q;
    memset(dw, inf, sizeof(dw));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '#') continue;
            for (int dr = 0; dr < 4; dr++) {
                int ni = i + rc[dr], nj = j + cc[dr];
                if (valid(ni, nj) && a[ni][nj] == '#') {
                    q.push({i, j});
                    dw[i][j] = 0;
                }
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + rc[i], ny = y + cc[i];
            if (valid(nx, ny) && a[nx][ny] != '#' && dw[nx][ny] > dw[x][y] + 1) {
                q.push({nx, ny});
                dw[nx][ny] = dw[x][y] + 1;
            }
        }
    }
}
void dijkstra() {
    memset(d, inf, sizeof(d));
    priority_queue<ar<int, 3>> pq;
    pq.push({0, sx, sy});
    d[sx][sy] = 0;
    while (!pq.empty()) {
        auto [w, x, y] = pq.top();
        pq.pop();
        if (-w != d[x][y]) continue;
        for (int i = 0; i < 4; ++i) {
            ar<int, 2> next;
            if (i == 0) next = lft[x][y];
            if (i == 1) next = rht[x][y];
            if (i == 2) next = up[x][y];
            if (i == 3) next = down[x][y];
            int nx = next[0], ny = next[1];
            int cost = d[x][y] + dw[x][y] + 1;
            if (valid(nx, ny) && a[nx][ny] != '#' && d[nx][ny] > cost) {
                d[nx][ny] = cost;
                pq.push({-cost, nx, ny});
            }
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + rc[i], ny = y + cc[i];
            int cost = d[x][y] + 1;
            if (valid(nx, ny) && a[nx][ny] != '#' && d[nx][ny] > cost) {
                d[nx][ny] = cost;
                pq.push({-cost, nx, ny});
            }
        }
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'S') sx = i, sy = j;
            if (a[i][j] == 'C') cx = i, cy = j;
        }
    }
    comp();
    bfs();
    dijkstra();
    cout << d[cx][cy];
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    while (t--) {
        solve();
        cout << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30