제출 #1121330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121330		PagodePaiva	포탈들 (BOI14_portals)	C++17	100 / 100	253 ms	34028 KiB

portals

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int mat[N][N];
int stx, sty, edx, edy;
int up[N][N], down[N][N], leftt[N][N], rightt[N][N];
int dist_paredes[N][N];
int r, c;
int dist[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool check(int a, int b){
    if(a < 0 or a > r+1 or b < 0 or b > c+1) return false;
    return true;
}

int main(){
    cin >> r >> c;
    for(int i = 1;i <= r;i++){
        for(int j = 1;j <= c;j++){
            char c;
            cin >> c;
            if(c == '#') continue;
            mat[i][j] = 1;
            if(c == 'S'){
                stx = i;
                sty = j;
            }
            if(c == 'C'){
                edx = i;
                edy = j;
            }
        }
    }
    for(int i = 1;i <= r;i++){
        int at = 0;
        for(int j = 1;j <= c;j++){
            leftt[i][j] = at+1;
            if(mat[i][j] == 0) at = j;
        }
    }
    for(int i = 1;i <= r;i++){
        int at = c+1;
        for(int j = c;j > 0;j--){
            rightt[i][j] = at-1;
            if(mat[i][j] == 0) at = j;
        }
    }
    for(int j = 1;j <= c;j++){
        int at = 0;
        for(int i = 1;i <= r;i++){
            up[i][j] = at+1;
            if(mat[i][j] == 0) at = i;
        }
    }
    for(int j = 1;j <= c;j++){
        int at = r+1;
        for(int i = r;i >= 1;i--){
            down[i][j] = at-1;
            if(mat[i][j] == 0) at = i;
        }
    }

    /*for(int i = 1;i <= r;i++){
        for(int j = 1;j <= c;j++){
            cout << i << ' ' << j << ":\n";
            cout << up[i][j] << ' ' << down[i][j] << ' ' << leftt[i][j] << ' ' << rightt[i][j] << '\n';
        }
    }*/
    memset(dist_paredes, -1, sizeof dist_paredes);
    queue <pair <int, int>> q;
    for(int i = 0;i <= r+1;i++){
        for(int j = 0;j <= c+1;j++){
            if(mat[i][j] == 0){
                dist_paredes[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        for(int i = 0;i < 4;i++){
            if(check(x+dx[i], y+dy[i])){
                if(dist_paredes[x+dx[i]][y+dy[i]] == -1){
                    dist_paredes[x+dx[i]][y+dy[i]] = dist_paredes[x][y]+1;
                    q.push({x+dx[i], y+dy[i]});
                }
            }
        }
    }
    for(int i = 0;i < r+2;i++){
        for(int j = 0;j < c+2;j++){
            dist[i][j] = 1e9;
        }
    }
    priority_queue <array <int, 3>> pq;
    pq.push({0, stx, sty});
    dist[stx][sty] = 0;
    while(!pq.empty()){
        auto [d, x, y] = pq.top();
        pq.pop();
        d *= -1;
        if(d != dist[x][y]) continue;
        //cout << d << ' ' << x << ' ' << y << '\n';
        for(int i = 0;i < 4;i++){
            if(check(x+dx[i], y+dy[i])){
                if(mat[x+dx[i]][y+dy[i]] == 0) continue;
                if(dist[x+dx[i]][y+dy[i]] > dist[x][y]+1){
                    dist[x+dx[i]][y+dy[i]] = dist[x][y]+1;
                    pq.push({-dist[x+dx[i]][y+dy[i]], x+dx[i], y+dy[i]});
                }
            }
        }
        int xx = up[x][y];
        if(dist[xx][y] > dist[x][y]+dist_paredes[x][y]){
            dist[xx][y] = dist[x][y]+dist_paredes[x][y];
            pq.push({-dist[xx][y], xx, y});
        }
        xx = down[x][y];
        if(dist[xx][y] > dist[x][y]+dist_paredes[x][y]){
            dist[xx][y] = dist[x][y]+dist_paredes[x][y];
            pq.push({-dist[xx][y], xx, y});
        }
        int yy = leftt[x][y];
        if(dist[x][yy] > dist[x][y]+dist_paredes[x][y]){
            dist[x][yy] = dist[x][y]+dist_paredes[x][y];
            pq.push({-dist[x][yy], x, yy});
        }
        yy = rightt[x][y];
        if(dist[x][yy] > dist[x][y]+dist_paredes[x][y]){
            dist[x][yy] = dist[x][y]+dist_paredes[x][y];
            pq.push({-dist[x][yy], x, yy});
        }
    }
    cout << dist[edx][edy] << '\n';
    return 0;
}   

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