Submission #1095717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095717		SoMotThanhXuan	Portals (BOI14_portals)	C++17	20 / 100	19 ms	27872 KiB

portals

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

int R, C;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int maxN = 1e3 + 2;
char a[1001][1001];
int val[1001][1001];
vector<int> adj[1000001];
int rem[1002];
int f[1000001];
bool isValid(int i, int j){
    return i >= 1 && i <= R && j >= 1 && j <= C && a[i][j] != '#';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> R >> C;
    int cnt = 0;
    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            cin >> a[i][j];
            val[i][j] = ++cnt;
        }
    }
    for(int j = 1; j <= C; ++j){
        for(int i = 1; i <= R; ++i){
            if(a[i][j] == '#'){
                rem[i] = i;
                continue;
            }
            rem[i] = rem[i - 1];
            int s = val[i][j], e = val[rem[i] + 1][j];
            if(s != e)adj[s].push_back(e);
        }
        rem[R + 1] = R + 1;
        for(int i = R; i >= 1; --i){
            if(a[i][j] == '#'){
                rem[i] = i;
                continue;
            }
            rem[i] = rem[i + 1];
            int s = val[i][j], e = val[rem[i] - 1][j];
            if(s != e)adj[s].push_back(e);
        }
    }
    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            if(a[i][j] == '#'){
                rem[j] = j;
                continue;
            }
            rem[j] = rem[j - 1];
            int s = val[i][j], e = val[i][rem[j] + 1];
            if(s != e)adj[s].push_back(e);
        }
        rem[C + 1] = C + 1;
        for(int j = C; j >= 1; --j){
            if(a[i][j] == '#'){
                rem[j] = j;
                continue;
            }
            rem[j] = rem[j + 1];
            int s = val[i][j], e = val[i][rem[j] - 1];
            if(s != e)adj[s].push_back(e);
        }
    }

    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            if(a[i][j] == '#')continue;
            for(int k = 0; k < 4; ++k){
                int ni = i + dx[k];
                int nj = j + dy[k];
                if(isValid(ni, nj))adj[val[i][j]].push_back(val[ni][nj]);
            }
        }
    }
    const int INF = 1e9 + 9;
    int s, e;
    for(int i = 1; i <= R; ++i)for(int j = 1; j <= C; ++j)if(a[i][j] == 'S')s = val[i][j]; else if(a[i][j] == 'C') e = val[i][j];
    for(int i = 1; i <= cnt; ++i)f[i] = INF;
    f[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
    Q.push({0, s});
    while(!Q.empty()){
        int p = Q.top().second;
        int dis = Q.top().first;
        Q.pop();
        if(dis > f[p])continue;
        for(int v: adj[p]){
            if(f[v] > f[p] + 1){
                f[v] = f[p] + 1;
                Q.push({f[v], v});
            }
        }
    }
    cout << f[e];
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:98:16: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     cout << f[e];
      |                ^

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