Submission #1095729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095729		SoMotThanhXuan	Portals (BOI14_portals)	C++17	20 / 100	25 ms	29788 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];
#define up fdoisofds
#define down odshfod
#define left ofdFDSJAO
#define right fioiofsiosdoisio
int up[1001][1001], down[1001][1001], left[1001][1001], right[1001][1001];
pair<int, int> td[1000001];
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;
            td[cnt] = {i, j};
        }
    }
    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];
            up[i][j] = val[rem[i] + 1][j];
        }
        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];
            down[i][j] = val[rem[i] - 1][j];
        }
    }
    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];
            left[i][j] = val[i][rem[j] + 1];
        }
        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];
            right[i][j] = val[i][rem[j] - 1];
        }
    }
    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            if(a[i][j] == '#')continue;
            int cur = val[i][j];
            for(int k = 0; k < 4; ++k){
                int ni = i + dx[k];
                int nj = j + dy[k];
                if(ni >= 1 && ni <= R && nj >= 1 && nj <= C){
                    if(a[ni][nj] != '#')adj[cur].push_back(val[ni][nj]);
                    else if(a[ni][nj] == '#'){
                        if(k == 0){
                            if(up[i][j])adj[cur].push_back(up[i][j]);
                            if(left[i][j])adj[cur].push_back(left[i][j]);
                            if(down[i][j])adj[cur].push_back(down[i][j]);
                        }else if(k == 1){
                            if(up[i][j])adj[cur].push_back(up[i][j]);
                            if(right[i][j])adj[cur].push_back(right[i][j]);
                            if(down[i][j])adj[cur].push_back(down[i][j]);
                        }else if(k == 2){
                            if(up[i][j])adj[cur].push_back(up[i][j]);
                            if(left[i][j])adj[cur].push_back(left[i][j]);
                            if(right[i][j])adj[cur].push_back(right[i][j]);
                        }else{
                            if(right[i][j])adj[cur].push_back(right[i][j]);
                            if(left[i][j])adj[cur].push_back(left[i][j]);
                            if(down[i][j])adj[cur].push_back(down[i][j]);
                        }
                    }
                }
                else{
                    if(k == 0){
                        if(up[i][j])adj[cur].push_back(up[i][j]);
                        if(left[i][j])adj[cur].push_back(left[i][j]);
                        if(down[i][j])adj[cur].push_back(down[i][j]);
                    }else if(k == 1){
                        if(up[i][j])adj[cur].push_back(up[i][j]);
                        if(right[i][j])adj[cur].push_back(right[i][j]);
                        if(down[i][j])adj[cur].push_back(down[i][j]);
                    }else if(k == 2){
                        if(up[i][j])adj[cur].push_back(up[i][j]);
                        if(left[i][j])adj[cur].push_back(left[i][j]);
                        if(right[i][j])adj[cur].push_back(right[i][j]);
                    }else{
                        if(right[i][j])adj[cur].push_back(right[i][j]);
                        if(left[i][j])adj[cur].push_back(left[i][j]);
                        if(down[i][j])adj[cur].push_back(down[i][j]);
                    }
                }
            }
        }
    }
    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:141:16: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |     cout << f[e];
      |                ^

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