oj.uz

Submission #942909

# Submission time Handle Problem Language Result Execution time Memory
942909 2024-03-11T06:48:44 Z beepbeepsheep Portals (BOI14_portals) C++17
20 / 100
 11 ms 25156 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
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};
        for (int j=0;j<=c+1;j++){
            if (grid[i][j]=='#')
                p={i,j+1};
            else wall[i][j][0]=p;
            //first open square
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        for (int j=0;j<=r+1;j++){

            if (grid[j][i]=='#'){
                p={j+1,i};
            }
            else wall[j][i][1]=p;
        }
    }
    for (int i=1;i<=r;i++){
        ii p={0,0};
        for (int j=c+1;j>=0;j--){
            if (grid[i][j]=='#')
                p={i,j-1};
            else wall[i][j][2]=p;
        }
    }
    for (int i=1;i<=c;i++){
        ii p={0,0};
        for (int j=r+1;j>=0;j--){
            if (grid[j][i]=='#'){
                p={j-1,i};
            }
            else wall[j][i][3]=p;
        }
    }
                        cerr<<1<<endl;
    queue<ii> q;
    q.emplace(s);
    memset(dis,-1,sizeof(dis));
    dis[s.first][s.second]=0;
    cerr<<1<<endl;
    while (q.size()){
        ll x,y;
        tie(x,y)=q.front();
        q.pop();
        for (int i=0;i<4;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 10584 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Incorrect 2 ms 12636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 6 ms 25156 KB Output is correct
7 Correct 7 ms 24920 KB Output is correct
8 Correct 4 ms 24920 KB Output is correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12760 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Incorrect 2 ms 12892 KB Output isn't correct
7 Halted 0 ms 0 KB -