oj.uz

Submission #879739

# Submission time Handle Problem Language Result Execution time Memory
879739 2023-11-28T03:34:30 Z 1075508020060209tc Portal (COCI17_portal) C++14
96 / 120
 41 ms 11324 KB 
//#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});
            dq.push_back({{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});
            dq.push_back({{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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9308 KB Output is correct
2 Correct 15 ms 7004 KB Output is correct
3 Correct 11 ms 6748 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9820 KB Output is correct
2 Correct 5 ms 10588 KB Output is correct
3 Correct 18 ms 7028 KB Output is correct
4 Incorrect 15 ms 9052 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 11324 KB Output isn't correct
2 Halted 0 ms 0 KB -