#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
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]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
13400 KB |
Output is correct |
| 2 |
Correct |
4 ms |
13404 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13404 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13500 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
13400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13400 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13400 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13404 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
13404 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 2 |
Correct |
4 ms |
13404 KB |
Output is correct |
| 3 |
Correct |
4 ms |
13404 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
13404 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13500 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
13404 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 3 |
Correct |
3 ms |
13404 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13404 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
13404 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
