oj.uz

Submission #673515

# Submission time Handle Problem Language Result Execution time Memory
673515 2022-12-20T19:50:40 Z AnasBenMoussa Portals (BOI14_portals) C++14
0 / 100
 15 ms 25060 KB 
        #include <bits/stdc++.h>
        #define int long long
        using namespace std;
        const int N=1005;
        char grid[N][N];
        int dis[N][N];
        const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};int x,y;
        vector<pair<int,int>>adj[N][N];
        void bfs(int r,int c){
           queue<pair<int,int>>q;
           for(int i=1;i<=x;i++){
                for(int j=1;j<=y;j++){
                    dis[i][j]=-1;
                }
           }
           dis[r][c]=0;
           q.push({r,c});
           while(!q.empty()){
                pair<int,int>u=q.front();q.pop();
                for(auto r:adj[u.first][u.second]){
                    if(dis[r.first][r.second]!=-1){
                        continue;
                    }
                    dis[r.first][r.second]=dis[u.first][u.second]+1;
                    q.push({r.first,r.second});
                }
           }
        }
        int32_t main(){
        ios_base::sync_with_stdio(false);cin.tie(NULL);
        cin>>x;cin>>y;int stx;int sty;int enx;int eny;
        memset(grid,'#',sizeof(grid));
        for(int i=1;i<=x;i++){
            for(int j=1;j<=y;j++){
                cin>>grid[i][j];
                if(grid[i][j]=='S'){
                    stx=i;sty=j;
                }
                if(grid[i][j]=='C'){
                    enx=i;eny=j;
                }
            }
        }
        for(int i=0;i<=x+1;i++){
            for(int j=0;j<=y+1;j++){
                if(grid[i][j]!='#'){
                for(int r=0;r<4;r++){
                    int newx=nx[r]+i;int newy=ny[r]+j;
                    if(newx>=1&&newx<=x&&newy>=1&&newy<=y&&grid[newx][newy]!='#'){
                        adj[i][j].push_back({newx,newy});
                    }
                }
                }
                if(grid[i][j]=='#'){
                    int l=i-1;
                    if(i!=0){
                        //up
                        while(l!=0){
                            if(grid[l-1][j]=='#'){
                                break;
                            }
                            l--;
                        }
                        if(l!=i-1&&i!=0){
                            adj[i-1][j].push_back({l,j});
                        }
                    }

                    //down
                    l=i+1;
                     while(l!=x+1){
                        if(grid[l+1][j]=='#'){
                            break;
                        }
                        l++;
                    }
                    if(l!=i+1){
                        adj[i+1][j].push_back({l,j});
                    }

                    //right
                   l=j+1;
                     while(l!=y+1){
                        if(grid[i][l+1]=='#'){
                            break;
                        }
                        l++;
                    }
                    if(l!=j+1){
                        adj[i][j+1].push_back({i,l});
                    }

                    //left
                    if(j!=0){
                        l=j-1;
                        while(l!=0){
                            if(grid[i][l-1]=='#'){
                                break;
                            }
                            l--;
                        }
                        if(l!=j-1&&j!=0){
                            adj[i][j-1].push_back({i,l});
                        }
                    }

                }
            }
        }
        bfs(stx,sty);
        cout<<dis[enx][eny]<<endl;
        return 0;

        }

Compilation message

portals.cpp: In function 'int32_t main()':
portals.cpp:111:27: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |         cout<<dis[enx][eny]<<endl;
      |                           ^
portals.cpp:111:27: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:110:12: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |         bfs(stx,sty);
      |         ~~~^~~~~~~~~
portals.cpp:110:12: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Correct 12 ms 25044 KB Output is correct
3 Correct 12 ms 25044 KB Output is correct
4 Correct 12 ms 24948 KB Output is correct
5 Incorrect 12 ms 25052 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24956 KB Output is correct
2 Correct 12 ms 25044 KB Output is correct
3 Correct 12 ms 25044 KB Output is correct
4 Correct 13 ms 25044 KB Output is correct
5 Incorrect 14 ms 25048 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 12 ms 25060 KB Output is correct
3 Correct 13 ms 25008 KB Output is correct
4 Correct 12 ms 25044 KB Output is correct
5 Incorrect 13 ms 25044 KB Output isn't correct
6 Halted 0 ms 0 KB -