Submission #1141461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141461		dpsaveslives	Portals (BOI14_portals)	C++20	100 / 100	164 ms	29252 KiB

portals

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
char grid[1005][1005];
int R,C;
int horw[1005][1005][2], vertw[1005][1005][2];
int dist[1005][1005],ans[1005][1005]; //distance to closest wall
int dr[4] = {0,0,1,-1}, dc[4] = {1,-1,0,0};
priority_queue<pair<int,pair<int,int>>> pq;
void upd(int r, int c, int nr, int nc, int nd){
    if(nr >= 1 && nr <= R && nc >= 1 && nc <= C && grid[nr][nc] != '#' && ((ans[nr][nc] == -1)||(ans[nr][nc] > ans[r][c]+nd))){
        ans[nr][nc] = ans[r][c]+nd;
        pq.push({-ans[nr][nc],{nr,nc}});
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> R >> C;
    queue<pair<int,int>> q;
    pair<int,int> tar;
    for(int i = 1;i<=R;++i){
        for(int j = 1;j<=C;++j){
            cin >> grid[i][j];
            dist[i][j] = ans[i][j] = -1;
            if(grid[i][j] == '#'){
                q.push({i,j});
                dist[i][j] = 0;
            }
            else if(grid[i][j] == 'S'){
                pq.push({0,{i,j}});
                ans[i][j] = 0;
            }
            else if(grid[i][j] == 'C'){
                tar = make_pair(i,j);
            }
        }
    }
    //q.push({0,0}); q.push({R+1,0}); q.push({R+1,C+1}); q.push({0,C+1});
    for(int i = 1;i<=R;++i){
        dist[i][0] = dist[i][C+1] = 0;
        q.push({i,0}); q.push({i,C+1});
    }
    for(int i = 1;i<=C;++i){
        dist[0][i] = dist[R+1][i] = 0;
        q.push({0,i}); q.push({R+1,i});
    }
    while(!q.empty()){
        int r = q.front().f, c = q.front().s; q.pop();
        //cout << r << " " << c << " " << dist[r][c] << "\n";
        for(int i = 0;i<4;++i){
            int nr = r+dr[i], nc = c+dc[i];
            if(nr >= 1 && nr <= R && nc >= 1 && nc <= C && dist[nr][nc] == -1){
                if(nr <= 0 || nr == R+1 || nc <= 0 || nc == C+1){
                    dist[nr][nc] = 1;
                    q.push({nr,nc});
                    continue;
                }
                dist[nr][nc] = dist[r][c]+1;
                q.push({nr,nc});
            }
        }
    }
    for(int i = 1;i<=R;++i){
        for(int j = 1;j<=C;++j){
            if(grid[i][j-1] == '#' || j == 1){
                horw[i][j][0] = j; //next wall to the left is (i,j-1)
            }
            else{
                horw[i][j][0] = horw[i][j-1][0]; //otherwise it's just whatever the other one's is
            }
            if(grid[i-1][j] == '#' || i == 1){
                vertw[i][j][0] = i; //next wall above us is (i-1,j)
            }
            else{
                vertw[i][j][0] = vertw[i-1][j][0];
            }
        }
    }
    for(int i = R;i>=1;--i){
        for(int j = C;j>=1;--j){
            if(grid[i][j+1] == '#' || j == C){
                horw[i][j][1] = j; //next wall to the right is (i,j+1)
            }
            else{
                horw[i][j][1] = horw[i][j+1][1]; //otherwise it's just whatever the other one's is
            }
            if(grid[i+1][j] == '#' || i == R){
                vertw[i][j][1] = i; //next wall above us is (i+1,j)
            }
            else{
                vertw[i][j][1] = vertw[i+1][j][1];
            }
        }
    }
    while(!pq.empty()){
        int r = pq.top().s.f, c = pq.top().s.s; pq.pop();
        //cout << r << " " << c << " " << ans[r][c] << "\n";
        if(grid[r][c] == 'C') break; //found!
        for(int i = 0;i<4;++i){
            int nr = r+dr[i], nc = c+dc[i];
            upd(r,c,nr,nc,1);
        }
        upd(r,c,vertw[r][c][0],c,dist[r][c]);
        upd(r,c,vertw[r][c][1],c,dist[r][c]);
        upd(r,c,r,horw[r][c][0],dist[r][c]);
        upd(r,c,r,horw[r][c][1],dist[r][c]);
    }
    cout << ans[tar.f][tar.s] << "\n";
    return 0;
}

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