Submission #769864

#	Time	Username	Problem	Language	Result	Execution time	Memory
769864		Ronin13	Portals (BOI14_portals)	C++17	100 / 100	719 ms	151688 KiB

portals

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;


int main(){
    int n, m; cin >> n >> m;
    char c[n + 1][m + 1];
    vector <pair<pii, int> > g[n + 1][m + 1];
    for(int i= 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            cin >> c[i][j];
    }
    int xs, ys;
    int xf, yf;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(c[i][j] == 'S') xs = i, ys = j;
            if(c[i][j] == 'C') xf = i, yf = j;
        }
    }

    queue <pii> q;
    int d[n + 1][m + 1];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            d[i][j] = 1e9;
            if(c[i][j] == '#'){
                d[i][j] = 0;
                q.push({i, j});
            }
        }
        d[i][0] = d[i][m + 1] = 0;
        q.push({i, 0});
        q.push({i, m + 1});
    }
    for(int i = 1; i <= m; i++){
        q.push({0, i});
        q.push({n + 1, i});
        d[0][i] = d[n + 1][i] = 0;
    }

    while(!q.empty()){
        int i = q.front().f;
        int j = q.front().s;
        q.pop();
        if(i > 1 && c[i - 1][j] != '#'){
            if(d[i - 1][j] > d[i][j] + 1)
            q.push({i - 1, j}), d[i - 1][j] = d[i][j] + 1;
        }
        if(i < n && c[i + 1][j] != '#'){
            if(d[i + 1][j] > d[i][j] + 1)
            q.push({i + 1, j}), d[i + 1][j] = d[i][j] + 1;
        }
        if(j > 1 && c[i][j - 1] != '#'){
            if(d[i][j - 1] > d[i][j] + 1)
            q.push({i, j - 1}), d[i][j - 1] = d[i][j] + 1;
        }
        if(j < m && c[i][j + 1] != '#'){
            if(d[i][j + 1] > d[i][j] + 1)
            q.push({i, j + 1}), d[i][j + 1] = d[i][j] + 1;
        }
    }



    for(int i = 1; i <= n; i++){
        int lst = 0;
        for(int j = 1; j <= m; j++){
            if(c[i][j] != '#' && ((j == 1) || (c[i][j - 1] == '#'))){
                lst = j;
            }
            g[i][j].pb({{i, lst}, d[i][j]});
        }
        lst = 0;
        for(int j = m; j >= 1; j--){
            if(c[i][j] != '#' && ((j == m) || (c[i][j + 1] == '#'))){
                lst = j;
            }
            g[i][j].pb({{i, lst}, d[i][j]});
        }
        for(int j = 1; j <= m; j++){
            if(j > 1 && c[i][j - 1] != '#') g[i][j].pb({{i, j - 1}, 1});
            if(j < m && c[i][j + 1] != '#') g[i][j].pb({{i, j + 1}, 1});
        }
    }

    for(int j = 1; j <= m; j++){
        int lst= 0;
        for(int i = 1; i <= n; i++){
            if(c[i][j] != '#' && (i == 1 || c[i - 1][j] == '#')){
                lst = i;
            }
            g[i][j].pb({{lst, j}, d[i][j]});
        }
        lst = 0;
        for(int i = n; i >= 1; i--){
            if(c[i][j] != '#' && (i == n || c[i + 1][j] == '#')){
                lst = i;
            }
            g[i][j].pb({{lst, j}, d[i][j]});
        }
        for(int i = 1; i <= n; ++i){
            if(i > 1 && c[i - 1][j] != '#'){
                g[i][j].pb({{i - 1, j}, 1});
            }
            if(i < n && c[i + 1][j] != '#'){
                g[i][j].pb({{i + 1, j}, 1});
            }
        }
    }
    int D[n + 1][m + 1];
    bool used[n + 1][m + 1];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            D[i][j] = 1e9;
            used[i][j] = false;
        }
    }
    D[xs][ys] = 0;
   // cout << xs << ' ' << ys << ' ' << xf << ' ' << yf << "\n";
    priority_queue <pair<int, pii> > pq;
    pq.push({0, {xs, ys}});
    while(!pq.empty()){
        int i = pq.top().s.f, j = pq.top().s.s;
        pq.pop();
        if(used[i][j]) continue;
        used[i][j] = false;
        for(auto ooo : g[i][j]){
            int x = ooo.f.f;
            int y = ooo.f.s;
            int l = ooo.s;
            if(D[x][y] > D[i][j] + l){
                D[x][y] = D[i][j] + l;
                pq.push({-D[x][y], {x, y}});
            }
        }
    }

    cout << D[xf][yf];
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:127:15: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     D[xs][ys] = 0;
      |     ~~~~~~~~~~^~~
portals.cpp:127:15: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:147:21: warning: 'xf' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |     cout << D[xf][yf];
      |                     ^
portals.cpp:147:21: warning: 'yf' 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