Submission #823565

#	Time	Username	Problem	Language	Result	Execution time	Memory
823565		serifefedartar	Portals (BOI14_portals)	C++17	0 / 100	1 ms	212 KiB

portals

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 2005

vector<vector<int>> grid, nU, nD, nL, nR, dist;
pair<int,int> S = {-1, -1}, T = {-1, -1};
int R, C;
void precalc() {
    for (int i = 1; i <= C; i++) {
        int nearest = 0;
        for (int j = 1; j <= R; j++) {
            if (grid[j][i])
                nU[j][i] = nearest;
            else
                nearest = j;
        }
    }
    for (int i = 1; i <= C; i++) {
        int nearest = R+1;
        for (int j = R; j >= 1; j--) {
            if (grid[j][i])
                nD[j][i] = nearest;
            else
                nearest = j;
        }
    }
    for (int i = 1; i <= R; i++) {
        int nearest = 0;
        for (int j = 1; j <= C; j++) {
            if (grid[i][j])
                nL[i][j] = nearest;
            else
                nearest = j;
        }
    }
    for (int i = 1; i <= R; i++) {
        int nearest = C+1;
        for (int j = C; j >= 1; j--) {
            if (grid[i][j])
                nR[i][j] = nearest;
            else
                nearest = j;
        }
    }
}

int main() {
    fast
    cin >> R >> C;

    grid = vector<vector<int>>(R+1, vector<int>(C+1));
    nU = vector<vector<int>>(R+1, vector<int>(C+1, 0));
    nD = vector<vector<int>>(R+1, vector<int>(C+1, 0));
    nL = vector<vector<int>>(R+1, vector<int>(C+1, 0));
    nR = vector<vector<int>>(R+1, vector<int>(C+1, 0));
    dist = vector<vector<int>>(R+1, vector<int>(C+1, 1e9));
    for (int i = 1; i <= R; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= C; j++) {
            if (s[j-1] != '#')
                grid[i][j] = 1;

            if (s[j-1] == 'S')
                S = {i, j};
            else if (s[j-1] == 'C')
                T = {i, j};
        }
    }
    precalc();
   

    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> q;
    dist[S.f][S.s] = 0;
    q.push({0, S});
    while (!q.empty()) {
        int row = q.top().s.f;
        int col = q.top().s.s;
        q.pop();

        int nRow = row-1;
        int nCol = col;
        if (nRow == 0 || grid[nRow][nCol] == 0)
            nRow = nD[row][col] - 1;

        if (dist[nRow][nCol] > dist[row][col] + 1) {
            dist[nRow][nCol] = dist[row][col] + 1;
            q.push({dist[nRow][nCol], {nRow, nCol}});
        }

        nRow = row+1;
        nCol = col;
        if (nRow == R + 1 || grid[nRow][nCol] == 0)
            nRow = nU[row][col] + 1;

        if (dist[nRow][nCol] > dist[row][col] + 1) {
            dist[nRow][nCol] = dist[row][col] + 1;
            q.push({dist[nRow][nCol], {nRow, nCol}});
        }

        nRow = row;
        nCol = col-1;
        if (nCol == 0 || grid[nRow][nCol] == 0)
            nCol = nR[row][col] - 1;

        if (dist[nRow][nCol] > dist[row][col] + 1) {
            dist[nRow][nCol] = dist[row][col] + 1;
            q.push({dist[nRow][nCol], {nRow, nCol}});
        }

        nRow = row;
        nCol = col+1;
        if (nCol == C + 1 || grid[nRow][nCol] == 0)
            nCol = nL[row][col] + 1;

        if (dist[nRow][nCol] > dist[row][col] + 1) {
            dist[nRow][nCol] = dist[row][col] + 1;
            q.push({dist[nRow][nCol], {nRow, nCol}});
        }
    }
    cout << dist[T.f][T.s] << "\n";
}

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