Submission #233959

#	Time	Username	Problem	Language	Result	Execution time	Memory
233959		parsa_mobed	Portals (BOI14_portals)	C++14	100 / 100	309 ms	29208 KiB

portals

#include <bits/stdc++.h>

using namespace std;
#define pii pair <int , int>
#define F first
#define S second
#define num(i, j) (i * (m + 1) + j)
#define IsAdjToWall(i, j) (!(A[i - 1][j] && A[i + 1][j] && A[i][j - 1] && A[i][j + 1]))
const int N = 1e3 + 5, inf = N*N;
int A[N][N], dis[N][N], sid[N][N], nxt[N][N][4], n, m, S, E;
pii dir[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void BFS() {
    for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) sid[i][j] = inf;
    queue <int> q;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        if (A[i][j] && IsAdjToWall(i, j)) sid[i][j] = 0, q.push(num(i, j));
    while (!q.empty()) {
        int x = q.front() / (m + 1), y = q.front() % (m + 1); q.pop();
        for (int i = 0; i < 4; i++) {
            int _x = x + dir[i].F, _y = y + dir[i].S;
            if (A[_x][_y] && sid[x][y] + 1 < sid[_x][_y])
                sid[_x][_y] = sid[x][y] + 1, q.push(num(_x, _y));
        }
    }
}
void Dijkstra() {
    for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) dis[i][j] = inf;
    priority_queue <pii, vector<pii>, greater<pii>> pq;
    dis[S / (m + 1)][S % (m + 1)] = 0;
    pq.push({0, S});
    while (!pq.empty()) {
        int x = pq.top().S / (m + 1), y = pq.top().S % (m + 1); pq.pop();
        for (int i = 0; i < 4; i++) {
            int _x = x + dir[i].F, _y = y + dir[i].S;
            if (A[_x][_y] && dis[x][y] + 1 < dis[_x][_y])
                dis[_x][_y] = dis[x][y] + 1, pq.push({dis[_x][_y], num(_x, _y)});
            _x = nxt[x][y][i] / (m + 1), _y = nxt[x][y][i] % (m + 1);
            if (A[_x][_y] && dis[x][y] + sid[x][y] + 1 < dis[_x][_y])
                dis[_x][_y] = dis[x][y] + sid[x][y] + 1, pq.push({dis[_x][_y], num(_x, _y)});
        }
    }
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        char c; cin >> c;
        if (c != '#') A[i][j] = 1;
        if (c == 'S') S = num(i, j);
        if (c == 'C') E = num(i, j);
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (A[i][j]) {
        nxt[i][j][0] = (A[i - 1][j] ? nxt[i - 1][j][0] : num(i, j));
        nxt[i][j][2] = (A[i][j - 1] ? nxt[i][j - 1][2] : num(i, j));
    }
    for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) if (A[i][j]) {
        nxt[i][j][1] = (A[i + 1][j] ? nxt[i + 1][j][1] : num(i, j));
        nxt[i][j][3] = (A[i][j + 1] ? nxt[i][j + 1][3] : num(i, j));
    }
    BFS(), Dijkstra();
    cout << dis[E / (m + 1)][E % (m + 1)] << "\n";
}

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