Submission #464761

#	Time	Username	Problem	Language	Result	Execution time	Memory
464761		JovanB	Portals (BOI14_portals)	C++17	100 / 100	359 ms	37096 KiB

portals

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

using ll = long long;
using ld = long double;

int di[] = {-1, 1, 0, 0};
int dj[] = {0, 0, -1, 1};

const int N = 1000;

int dist[N+5][N+5];
int wall[N+5][N+5];
int dole[N+5][N+5], gore[N+5][N+5], levo[N+5][N+5], desno[N+5][N+5];
int mat[N+5][N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    int si, sj, ti, tj;
    for(int i=1; i<=n; i++){
        string s;
        cin >> s;
        for(int j=1; j<=m; j++){
            if(s[j-1] != '#') mat[i][j] = 1;
            if(s[j-1] == 'S') si = i, sj = j;
            else if(s[j-1] == 'C') ti = i, tj = j;
        }
    }
    queue <pair <int, int>> zid;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            bool pored = 0;
            for(int d=0; d<4; d++){
                int ci = i + di[d];
                int cj = j + dj[d];
                if(!mat[ci][cj]) pored = 1;
            }
            if(pored){
                wall[i][j] = 1;
                zid.push({i, j});
            }
            else wall[i][j] = N*N+5;
        }
    }
    while(!zid.empty()){
        int vi, vj;
        tie(vi, vj) = zid.front();
        zid.pop();
        for(int d=0; d<4; d++){
            int ci = vi + di[d];
            int cj = vj + dj[d];
            if(mat[ci][cj] && wall[ci][cj] > wall[vi][vj] + 1){
                wall[ci][cj] = wall[vi][vj] + 1;
                zid.push({ci, cj});
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(mat[i][j-1]) levo[i][j] = levo[i][j-1];
            else levo[i][j] = j;
        }
        for(int j=m; j>=1; j--){
            if(mat[i][j+1]) desno[i][j] = desno[i][j+1];
            else desno[i][j] = j;
        }
    }
    for(int j=1; j<=m; j++){
        for(int i=1; i<=n; i++){
            if(mat[i-1][j]) gore[i][j] = gore[i-1][j];
            else gore[i][j] = i;
        }
        for(int i=n; i>=1; i--){
            if(mat[i+1][j]) dole[i][j] = dole[i+1][j];
            else dole[i][j] = i;
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(mat[i][j]) dist[i][j] = N*N+5;
        }
    }
    using T = tuple <int, int, int>;
    priority_queue <T, vector <T>, greater <T>> q;
    dist[si][sj] = 0;
    q.push(make_tuple(0, si, sj));
    while(!q.empty()){
        int ds, vi, vj;
        tie(ds, vi, vj) = q.top();
        q.pop();
        if(ds != dist[vi][vj]) continue;
        for(int d=0; d<4; d++){
            int ci = vi + di[d];
            int cj = vj + dj[d];
            if(dist[ci][cj] > dist[vi][vj] + 1){
                dist[ci][cj] = dist[vi][vj] + 1;
                q.push(make_tuple(dist[ci][cj], ci, cj));
            }
        }
        int k = levo[vi][vj];
        if(dist[vi][k] > dist[vi][vj] + wall[vi][vj]){
            dist[vi][k] = dist[vi][vj] + wall[vi][vj];
            q.push(make_tuple(dist[vi][k], vi, k));
        }
        k = desno[vi][vj];
        if(dist[vi][k] > dist[vi][vj] + wall[vi][vj]){
            dist[vi][k] = dist[vi][vj] + wall[vi][vj];
            q.push(make_tuple(dist[vi][k], vi, k));
        }
        k = gore[vi][vj];
        if(dist[k][vj] > dist[vi][vj] + wall[vi][vj]){
            dist[k][vj] = dist[vi][vj] + wall[vi][vj];
            q.push(make_tuple(dist[k][vj], k, vj));
        }
        k = dole[vi][vj];
        if(dist[k][vj] > dist[vi][vj] + wall[vi][vj]){
            dist[k][vj] = dist[vi][vj] + wall[vi][vj];
            q.push(make_tuple(dist[k][vj], k, vj));
        }
    }
    cout << dist[ti][tj] << "\n";
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:126:29: warning: 'tj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |     cout << dist[ti][tj] << "\n";
      |                             ^~~~
portals.cpp:126:29: warning: 'ti' may be used uninitialized in this function [-Wmaybe-uninitialized]

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