Submission #823606

#	Time	Username	Problem	Language	Result	Execution time	Memory
823606		serifefedartar	Portals (BOI14_portals)	C++17	100 / 100	309 ms	25456 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;
        }

        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};
        vector<pair<int,int>> v = {d1, d2, d3, d4};
        for (int from = 0; from < 4; from++) {
            for (int to = 0; to < 4; to++) {
                pair<int,int> from_p = v[from];
                pair<int,int> to_p = v[to];

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

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:90:14: warning: variable 'wall' set but not used [-Wunused-but-set-variable]
   90 |         bool wall = false;
      |              ^~~~

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