제출 #1175016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175016		ThommyDB	포탈들 (BOI14_portals)	C++20	0 / 100	0 ms	328 KiB

portals

#include<bits/stdc++.h>

using namespace std;

int r, c;
vector<vector<char>> grid;
vector<vector<pair<pair<int, int>, pair<int, int>>>> teleport;

signed main(){
    cin >> r >> c;
    grid.resize(r, vector<char>(c));
    teleport.resize(r, vector<pair<pair<int, int>, pair<int, int>>>(c, {{-1, -1}, {-1, -1}}));
    priority_queue<pair<int, pair<int, int>>> q;
    pair<int, int> cakePos;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> grid[i][j];
            if(i==0)teleport[i][j].second.first=0;
            if(j==0)teleport[i][j].first.first=0;
            if(grid[i][j] != '#' && i!=0) teleport[i][j].second.first=teleport[i-1][j].second.first+1;
            if(grid[i][j] != '#' && j!=0) teleport[i][j].first.first=teleport[i][j-1].first.first+1;

            if(grid[i][j]=='S') q.push({0, {i, j}});
            if(grid[i][j]=='C') cakePos = {i, j};
        }
    }
    for(int i = r-2; i >= 0; i--){
        for(int j = c-2; j >= 0; j--){
            if(i==r-1)teleport[i][j].second.second=0;
            if(j==c-1)teleport[i][j].first.second=0;
            if(grid[i][j] != '#')teleport[i][j].second.second=teleport[i+1][j].second.second+1;
            if(grid[i][j] != '#')teleport[i][j].first.second=teleport[i][j+1].first.second+1;
        }
    }

    vector<vector<int>> dist(r, vector<int>(c, INT_MAX));
    vector<vector<bool>> visited(r, vector<bool>(c));
    vector<pair<int, int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    while(!q.empty()){
        int d = -q.top().first; int i = q.top().second.first; int j = q.top().second.second; q.pop();
        //cout << "d: " << d << "\n";
        //cout << "i: " << i << "\n";
        //cout << "j: " << j << "\n";
        if(visited[i][j]) continue;
        visited[i][j]=true;
        /*if(i==0 && j==2){
            cout << teleport[i][j].first.first << " & " << teleport[i][j].first.second << " & " << teleport[i][j].second.first << " & " << teleport[i][j].second.second << "\n";
        }*/
        for(auto u : dir){
            if(i+u.first <0 || j+u.second<0 ||i+u.first>r-1 || j+u.second>c-1) continue;
            if(grid[i+u.first][j+u.second]!='#'){
                if(dist[i+u.first][j+u.second]>d+1){
                    dist[i+u.first][j+u.second]=d+1;
                    q.push({-d-1, {i+u.first, j+u.second}});
                }
            }
        }
        int mn=min({teleport[i][j].first.first, teleport[i][j].first.second, teleport[i][j].second.first, teleport[i][j].second.second})+1;
        if(!(i-teleport[i][j].second.first ==-1 || j==-1 ||i-teleport[i][j].second.first==r || j==c) && grid[i-teleport[i][j].second.first][j]!='#'){
            if(dist[i-teleport[i][j].second.first][j]>d+mn){
                dist[i-teleport[i][j].second.first][j]=d+mn+1;
                q.push({-d-mn-1, {i-teleport[i][j].second.first, j}});
            }
        }
        if(!(i+teleport[i][j].second.second ==-1 || j==-1 ||i+teleport[i][j].second.second==r || j==c) && grid[i+teleport[i][j].second.second][j]!='#'){
            if(dist[i+teleport[i][j].second.second][j]>d+mn){
                dist[i+teleport[i][j].second.second][j]=d+mn+1;
                q.push({-d-mn-1, {i+teleport[i][j].second.second, j}});
            }
        }
        if(!(i ==-1 || j-teleport[i][j].first.first==-1 ||i==r || j-teleport[i][j].first.first==c) && grid[i][j-teleport[i][j].first.first]!='#'){
            if(dist[i][j-teleport[i][j].first.first]>d+mn){
                dist[i][j-teleport[i][j].first.first]=d+mn+1;
                q.push({-d-mn-1, {i, j-teleport[i][j].first.first}});
            }
        }
        if(!(i ==-1 || j+teleport[i][j].first.second==-1 ||i==r || j+teleport[i][j].first.second==c) && grid[i][j+teleport[i][j].first.second]!='#'){
            if(dist[i][j+teleport[i][j].first.second]>d+mn){
                dist[i][j+teleport[i][j].first.second]=d+mn+1;
                q.push({-d-mn-1, {i, j+teleport[i][j].first.second}});
            }
        }
        //cout << "q: "<< q.size() << "\n";
    }
    /*for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }*/
    int ans = dist[cakePos.first][cakePos.second];
    cout << ans << "\n";
}

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