Submission #912818

#	Time	Username	Problem	Language	Result	Execution time	Memory
912818		1075508020060209tc	Portals (BOI14_portals)	C++14	0 / 100	4 ms	13660 KiB

portals

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
#define SZ(x) (int)(x).size()
int n;int m;
string gr[200005];
int dir[5]={0,1,0,-1,0};
pair<int,int>dp[1010][1010][4];
int ok(int x,int y){
if(x>=1&&y>=1&&x<=n&&y<=m){return 1;}
return 0;
}
int ndis[1010][1010];
void buildnear(){

queue<pair<int,int>>q;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        ndis[i][j]=1e18;
        if(gr[i][j]=='#'){continue;}
        int fok=0;
        for(int d=0;d<=3;d++){
            int x=i+dir[d];int y=j+dir[d+1];
            if(!ok(x,y)||gr[x][y]=='#'){
                fok=1;
            }
        }
        if(fok){
            q.push({i,j});
            ndis[i][j]=0;
        }
    }
}

while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop();
    for(int d=0;d<=3;d++){
        int x=nwx+dir[d];int y=nwy+dir[d+1];
        if(ndis[x][y]>12345678){
            ndis[x][y]=ndis[nwx][nwy]+1;
            q.push({x,y});
        }
    }
}

}


void builddp(){
for(int i=1;i<=n;i++){
    for(int j=m;j>=1;j--){
        if(gr[i][j]=='#'){dp[i][j][0]={-1,-1};}
        int x=i+0;int y=j+1;
        if(!ok(x,y)||gr[x][y]=='#'){
            dp[i][j][0]={i,j};
        }else{
            dp[i][j][0]=dp[i][j+1][0];
        }
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(gr[i][j]=='#'){dp[i][j][2]={-1,-1};}
        int x=i+0;int y=j-1;
        if(!ok(x,y)||gr[x][y]=='#'){
            dp[i][j][2]={i,j};
        }else{
            dp[i][j][2]=dp[i][j-1][2];
        }
    }
}
//
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(gr[i][j]=='#'){dp[i][j][4]={-1,-1};}
        int x=i-1;int y=j;
        if(!ok(x,y)||gr[x][y]=='#'){
            dp[i][j][3]={i,j};
        }else{
            dp[i][j][3]=dp[i-1][j][3];
        }
    }
}
for(int i=n;i>=1;i--){
    for(int j=1;j<=m;j++){
        if(gr[i][j]=='#'){dp[i][j][1]={-1,-1};}
        int x=i+1;int y=j;
        if(!ok(x,y)||gr[x][y]=='#'){
            dp[i][j][1]={i,j};
        }else{
            dp[i][j][1]=dp[i+1][j][1];
        }
    }
}
}
int dis[1010][1010];
bool vis[1010][1010];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>gr[i];
    gr[i]='#'+gr[i]+"#";
}
gr[0]="";gr[n+1]="";
for(int i=1;i<=m;i++){
    gr[0]+="#";
    gr[n+1]+="#";
}
builddp();
buildnear();
int stx;int sty;int enx;int eny;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(gr[i][j]=='S'){
            stx=i;sty=j;
        }
        if(gr[i][j]=='C'){
            enx=i;eny=j;
        }
        dis[i][j]=1e12;
    }
}
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>> ,greater<pair<int,pair<int,int>>>  >q;
q.push({0,{stx,sty}});
dis[stx][sty]=0;
//cout<<"hehe\n";
while(q.size()){
    int nwx=q.top().second.first;
    int nwy=q.top().second.second;
    q.pop();
    if(vis[nwx][nwy]){continue;}
    vis[nwx][nwy]=1;
    for(int d=0;d<=3;d++){
        int x=nwx+dir[d];int y=nwy+dir[d+1];
        if(vis[x][y]){continue;}
        if(!ok(x,y)||gr[x][y]=='#'){continue;}
        dis[x][y]=min(dis[x][y],dis[nwx][nwy]+1);
        if(dis[x][y]==dis[nwx][nwy]+1){
            q.push({dis[x][y],{x,y}});
        }
    }
    for(int d=0;d<=3;d++){
        int x=dp[nwx][nwy][d].first;
        int y=dp[nwx][nwy][d].second;
        if(vis[x][y]){continue;}
        dis[x][y]=min(dis[x][y],dis[nwx][nwy]+ndis[nwx][nwy]+1);
        if(dis[x][y]==dis[nwx][nwy]+ndis[nwx][nwy]+1){
            q.push({dis[x][y],{x,y}});
        }
    }
}
cout<<dis[enx][eny]<<"\n";
}

Compilation message (stderr)

portals.cpp: In function 'void builddp()':
portals.cpp:80:37: warning: array subscript 4 is above array bounds of 'std::pair<long long int, long long int> [4]' [-Warray-bounds]
   80 |         if(gr[i][j]=='#'){dp[i][j][4]={-1,-1};}
      |                           ~~~~~~~~~~^
portals.cpp:80:37: warning: array subscript 4 is above array bounds of 'std::pair<long long int, long long int> [4]' [-Warray-bounds]
portals.cpp: In function 'int main()':
portals.cpp:130:14: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  130 | dis[stx][sty]=0;
      | ~~~~~~~~~~~~~^~
portals.cpp:130:14: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:157:19: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 | cout<<dis[enx][eny]<<"\n";
      |                   ^
portals.cpp:157:19: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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