oj.uz

Submission #942911

# Submission time Handle Problem Language Result Execution time Memory
942911 2024-03-11T06:52:42 Z beepbeepsheep Portals (BOI14_portals) C++17
0 / 100
 3 ms 10844 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>

const ll maxn=1005;
char grid[maxn][maxn];
ll dis[maxn][maxn];
ii wall[maxn][maxn][4]; //N,E,S,W
bool hasWall[maxn][maxn];
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll r,c;
    ii s,e;
    cin>>r>>c;
    for (int i=0;i<=r+1;i++){
        for (int j=0;j<=c+1;j++){
            grid[i][j]='#';
        }
    }
    for (int i=1;i<=r;i++){
        for (int j=1;j<=c;j++){
            cin>>grid[i][j];
            if (grid[i][j]=='S') s={i,j};
            if (grid[i][j]=='C') e={i,j};
        }
    }
    for (int i=1;i<=r;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=0;j<=c+1;j++){
            if (grid[i][j]=='#')
                p={i,j+1},ok=true;
            else{
                wall[i][j][0]=p;
                hasWall[i][j]=ok;
                ok=false;
            }
            //first open square
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=0;j<=r+1;j++){
            if (grid[j][i]=='#'){
                p={j+1,i},ok=true;
            }
            else{
                wall[j][i][1]=p;
                hasWall[j][i]=ok;
                ok=false;
            }
        }
    }
    for (int i=1;i<=r;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=c+1;j>=0;j--){
            if (grid[i][j]=='#')
                p={i,j-1},ok=true;
            else{
                wall[i][j][2]=p;
                hasWall[i][j]=ok;
                ok=false;
            }
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        bool ok=false;
        for (int j=r+1;j>=0;j--){
            if (grid[j][i]=='#'){
                p={j-1,i};
                ok=true;
            }
            else{
                wall[j][i][3]=p;
                hasWall[j][i]=ok;
                ok=false;
            }
        }
    }
    queue<ii> q;
    q.emplace(s);
    memset(dis,-1,sizeof(dis));
    dis[s.first][s.second]=0;
    while (q.size()){
        ll x,y;
        tie(x,y)=q.front();
        q.pop();
        for (int i=0;i<4 && hasWall[x][y];i++){
            ll nx=wall[x][y][i].first,ny=wall[x][y][i].second;
            if (dis[nx][ny]!=-1) continue;
            dis[nx][ny]=dis[x][y]+1;
            q.emplace(nx,ny);
        }
        for (int i=0;i<4;i++){
            ll nx=x+dx[i],ny=y+dy[i];
            if (grid[nx][ny]=='#') continue;
            if (dis[nx][ny]!=-1) continue;
            dis[nx][ny]=dis[x][y]+1;
            q.emplace(nx,ny);
        }
    }
    cout<<dis[e.first][e.second];
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 1 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 2 ms 10840 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 2 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Incorrect 2 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 2 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -