제출 #941010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941010		Sir_Ahmed_Imran	포탈들 (BOI14_portals)	C++17	70 / 100	370 ms	64220 KiB

portals

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define N 1004
char a[N][N];
pii UP[N][N];
pii DOWN[N][N];
pii LEFT[N][N];
pii RIGHT[N][N];
int dist[N][N];
bool vis[N][N];
vector<pii> mov{{-1,0},{0,-1},{0,1},{1,0}};
void solve(){
    pii pi;
    vector<pii> v,u;
    int n,m,p,q,r,x,y;
    cin>>n>>m;
    for(int i=0;i<n+4;i++){
        v.append({i,1});
        v.append({i,m+2});
        a[i][1]=a[i][m+2]='#';
        vis[i][1]=vis[i][m+2]=1;
    }
    for(int i=0;i<m+4;i++){
        v.append({1,i});
        v.append({n+2,i});
        a[1][i]=a[n+2][i]='#';
        vis[1][i]=vis[n+2][i]=1;
    }
    for(int i=2;i<n+2;i++){
        for(int j=2;j<m+2;j++){
            cin>>a[i][j];
            if(a[i][j]=='#'){
                vis[i][j]=1;
                v.append({i,j});
            }
            else dist[i][j]=1e9;
            if(a[i][j]=='S'){
                p=i;
                q=j;
            }
            if(a[i][j]=='C'){
                x=i;
                y=j;
            }
        }
    }
    for(int i=0;i<n*m;i++){
        if(v.empty()) break;
        for(auto& j:v){
            dist[j.ff][j.ss]=i;
            for(auto k:mov){
                pi=j;
                pi.ff+=k.ff;
                pi.ss+=k.ss;
                if(dist[pi.ff][pi.ss]>i+1){
                    dist[pi.ff][pi.ss]=i+1;
                    u.append(pi);
                }
            }
        }
        swap(v,u);
        u.clear();
    }
    for(int i=2;i<n+2;i++){
        for(int j=2;j<m+2;j++){
            UP[i][j]=UP[i-1][j];
            if(a[i-1][j]=='#')
                UP[i][j]={i,j};
            LEFT[i][j]=LEFT[i][j-1];
            if(a[i][j-1]=='#')
                LEFT[i][j]={i,j};
        }
    }
    for(int i=n+1;i>1;i--){
        for(int j=m+1;j>1;j--){
            DOWN[i][j]=DOWN[i+1][j];
            if(a[i+1][j]=='#')
                DOWN[i][j]={i,j};
            RIGHT[i][j]=RIGHT[i][j+1];
            if(a[i][j+1]=='#')
                RIGHT[i][j]={i,j};
        }
    }
    pi={x,y};
    priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> Q; 
    Q.push({0,{p,q}});
    while(Q.top().ss!=pi){
        p=Q.top().ss.ff;
        q=Q.top().ss.ss;
        r=Q.top().ff;
        Q.pop();
        if(!vis[p][q]){
            vis[p][q]=1;
            for(auto& i:mov){
                if(!vis[p+i.ff][q+i.ss])
                    Q.push({r+1,{p+i.ff,q+i.ss}});
            }
            if(!vis[UP[p][q].ff][UP[p][q].ss])
                    Q.push({r+dist[p][q],{UP[p][q].ff,UP[p][q].ss}});
            if(!vis[LEFT[p][q].ff][LEFT[p][q].ss])
                    Q.push({r+dist[p][q],{LEFT[p][q].ff,LEFT[p][q].ss}});
            if(!vis[DOWN[p][q].ff][DOWN[p][q].ss])
                    Q.push({r+dist[p][q],{DOWN[p][q].ff,DOWN[p][q].ss}});
            if(!vis[RIGHT[p][q].ff][RIGHT[p][q].ss])
                    Q.push({r+dist[p][q],{RIGHT[p][q].ff,RIGHT[p][q].ss}});
        }
    }
    cout<<Q.top().ff;
}
int main(){
    solve();
    return 0;
}

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