Submission #823570

#	Time	Username	Problem	Language	Result	Execution time	Memory
823570		serifefedartar	Portals (BOI14_portals)	C++17	20 / 100	5 ms	1492 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

const int delRow[] = {-1, 1, 0, 0};
const int delCol[] = {0, 0, -1, 1};
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();

        bool wall = false;
        for (int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];

            if (nRow > 0 && nCol > 0 && nRow <= R && nCol <= C && grid[nRow][nCol]) {
                if (dist[nRow][nCol] > dist[row][col] + 1) {
                    dist[nRow][nCol] = dist[row][col] + 1;
                    q.push({dist[nRow][nCol], {nRow, nCol}});
                }
            } else
                wall = true;
        }

        if (wall) {
            pair<int,int> d1 = {row, nL[row][col] + 1};
            pair<int,int> d2 = {row, nR[row][col] - 1};
            pair<int,int> d3 = {nU[row][col] + 1, col};
            pair<int,int> d4 = {nD[row][col] - 1, col};

            if (dist[d1.f][d1.s] > dist[row][col] + 1) {
                dist[d1.f][d1.s] = dist[row][col] + 1;
                q.push({dist[d1.f][d1.s], d1});
            }

            if (dist[d2.f][d2.s] > dist[row][col] + 1) {
                dist[d2.f][d2.s] = dist[row][col] + 1;
                q.push({dist[d2.f][d2.s], d2});
            }

            if (dist[d3.f][d3.s] > dist[row][col] + 1) {
                dist[d3.f][d3.s] = dist[row][col] + 1;
                q.push({dist[d3.f][d3.s], d3});
            }

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

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