Submission #879735

#	Time	Username	Problem	Language	Result	Execution time	Memory
879735		1075508020060209tc	Portal (COCI17_portal)	C++14	96 / 120	33 ms	10844 KiB

portal

//#pragma gcc optimize("O2")
#include <bits/stdc++.h>
//#include<complex>
using namespace std;
#define int long long
int n;int m;
string gr[510];
int dir[5]={0,1,0,-1,0};
int dis[510][510][5];

int bsd(int x,int y){
for(int d=1;d<=4;d++){
    int a=x+dir[d-1];int b=y+dir[d];
    if(gr[a][b]=='#'){return 1;}
}
return 0;
}

signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>gr[i];
    gr[i]="*"+gr[i];
}
pair<int,int>st;
pair<int,int>en;
deque<pair<pair<int,int>,int>>dq;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        for(int d=0;d<=4;d++){
            dis[i][j][d]=1e9;
        }
        if(gr[i][j]=='C'){
            st={i,j};
            dis[i][j][0]=0;
            dq.push_back({{i,j},0});
        }
        if(gr[i][j]=='F'){
            en={i,j};
        }
    }
}
while(dq.size()){
    int nwx=dq.front().first.first;
    int nwy=dq.front().first.second;
    int dr=dq.front().second;
    dq.pop_front();
  //  cout<<nwx<<" "<<nwy<<" "<<dr<<" "<<dis[nwx][nwy][dr]<<"\n";
    if(dr==0){
        for(int d=1;d<=4;d++){
            int x=nwx+dir[d-1];int y=nwy+dir[d];
            if(gr[x][y]=='#'){continue;}
            if(dis[x][y][0]>dis[nwx][nwy][0]+1){
                dis[x][y][0]=dis[nwx][nwy][0]+1;
                dq.push_back({{x,y},0});
            }
        }
        if(bsd(nwx,nwy)){
            for(int d=1;d<=4;d++){
                if(dis[nwx][nwy][d]>dis[nwx][nwy][0]+1){
                    dis[nwx][nwy][d]=dis[nwx][nwy][0]+1;
                    dq.push_back({{nwx,nwy},d});
                }
            }
        }
        continue;
    }
    int x;int y;
    x=nwx+dir[dr-1];y=nwy+dir[dr];
    if(gr[x][y]!='#'){
        if(dis[x][y][dr]>dis[nwx][nwy][dr]){
            dis[x][y][dr]=dis[nwx][nwy][dr];
            dq.push_front({{x,y},dr});
        }
    }else{
        if(dis[nwx][nwy][0]>dis[nwx][nwy][dr]){
            dis[nwx][nwy][0]=dis[nwx][nwy][dr];
            dq.push_front({{nwx,nwy},0});
        }
    }
}

if(dis[en.first][en.second][0]>1e8){
    cout<<"nemoguce";return 0;
}/*
for(int k=0;k<=4;k++){
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<dis[i][j][k]<<" ";
    }cout<<"\n";
}cout<<"\n";
}*/
cout<<dis[en.first][en.second][0]<<endl;

}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12