Submission #943341

#	Time	Username	Problem	Language	Result	Execution time	Memory
943341		ArashJafariyan	Portals (BOI14_portals)	C++17	100 / 100	582 ms	176464 KiB

portals

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

#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 0
#endif

#define pb push_back
#define i2 array<int, 2>
#define i3 array<int, 3>
#define ll long long

const int N = 1e3 + 8, dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};

int R, C, sr, sc, cr, cc, wall[N][N], dist[N][N];
bool mark[N][N];
i2 W[N][N][4];
char a[N][N];
vector<i3> adj[N][N];

bool ok(int r, int c) {
    return (r <= R && c <= C && r >= 0 && c >= 0);
}

bool ko(int r, int c) {
    return ok(r, c) && a[r][c] != '#';
}

void bfs() {
    queue<i2> q;
    for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= C; j++) {
            if (a[i][j] == '#') {
                wall[i][j] = 0;
                q.push({i, j});
            }   
        }
    }

    while (q.size()) {
        auto [r, c] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (ok(nr, nc) && wall[nr][nc] == -1) {
                wall[nr][nc] = wall[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    /* for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= C; j++) {
            wall[i][j]--;
        }
    } */
}

void work() {
    i2 last;
    for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= C; j++) {
            if (a[i][j] == '#') {
                last = {i, j + 1};
            }
            W[i][j][3] = last;
        }
    }
    for (int i = 0; i <= R; i++) {
        for (int j = C; j >= 0; j--) {
            if (a[i][j] == '#') {
                last = {i, j - 1};;
            }
            W[i][j][1] = last;
        }
    }
    for (int j = 0; j <= C; j++) {
        for (int i = 0; i <= R; i++) {
            if (a[i][j] == '#') {
                last = {i + 1, j};
            }
            W[i][j][0] = last;
        }
    }
    for (int j = 0; j <= C; j++) {
        for (int i = R; i >= 0; i--) {
            if (a[i][j] == '#') {
                last = {i - 1, j};
            }
            W[i][j][2] = last;
        }
    }
    
    for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= C; j++) {
            if (a[i][j] != '#') {
                for (int x = 0; x < 4; x++) {
                    if (ko(i + dr[x], j + dc[x])) {
                        adj[i][j].pb({i + dr[x], j + dc[x], 1});
                    }
                }
                for (int x = 0; x < 4; x++) {
                    adj[i][j].pb({W[i][j][x][0], W[i][j][x][1], wall[i][j]});
                }
            }
        }
    }
}

void dijkstra() {
    set<i3> s;
    s.insert({0, sr, sc});
    dist[sr][sc] = 0;
    
    while (s.size()) {
        auto [w, r, c] = *s.begin();
        s.erase(s.begin());

        if (mark[r][c]) {
            continue;
        }
        mark[r][c] = 1;

        for (auto [nr, nc, w] : adj[r][c]) {
            if (dist[r][c] + w < dist[nr][nc]) {
                dist[nr][nc] = dist[r][c] + w;
                s.insert({dist[nr][nc], nr, nc});
            }
        }
    }
}

void solve() {
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {a[i][j] = '#'; wall[i][j] = -1; dist[i][j] = N * N;}
    cin >> R >> C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'S') {
                sr = i;
                sc = j;
            }
            if (a[i][j] == 'C') {
                cr = i;
                cc = j;
            }
        }
    }
    R++; C++;    
    bfs();
    work();
    dijkstra();
    
    /* for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= C; j++) {
            cerr << dist[i][j] << ' ';
        }
        cerr << '\n';
    } */
    cout << dist[cr][cc];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

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