Submission #673542

#	Time	Username	Problem	Language	Result	Execution time	Memory
673542		AnasBenMoussa	Portals (BOI14_portals)	C++14	0 / 100	65 ms	96240 KiB

portals

            #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;
            set<pair<int,pair<int,int>>>adj[N][N];set<pair<int,pair<int,int>>>se[N][N];
                void dijsktra(int r,int c){
                int vis[x+1][y+1];
                for(int i=1;i<=x;i++){
                    for(int j=1;j<=y;j++){
                        vis[i][j]=0;dis[i][j]=INT_MAX;
                    }
                }
                set<pair<int,pair<int,int>>>ve;
                ve.insert({0,{r,c}});
                dis[r][c]=0;
                while(!ve.empty()){
                    pair<int,pair<int,int>>q=*(ve.begin());
                    ve.erase(*(ve.begin()));
                    if(vis[q.second.first][q.second.second]){
                        continue;
                    }
                    vis[q.second.first][q.second.second]=1;
                    for(auto i:se[q.second.first][q.second.second]){
                        for(auto j:se[q.second.first][q.second.second]){
                            if(i==j){
                                continue;
                            }
                            if(dis[i.second.first][i.second.second]>j.first+q.first+1){
                                dis[i.second.first][i.second.second]=j.first+q.first+1;
                                ve.insert({dis[i.second.first][i.second.second],{i.second.first,i.second.second}});
                            }
                             if(dis[j.second.first][j.second.second]>i.first+q.first+1){
                                dis[j.second.first][j.second.second]=i.first+q.first+1;
                                ve.insert({dis[j.second.first][j.second.second],{j.second.first,j.second.second}});
                            }
                        }
                    }
                    for(auto u:adj[q.second.first][q.second.second]){
                        if(dis[u.second.first][u.second.second]>q.first+u.first){
                            dis[u.second.first][u.second.second]=q.first+u.first;
                            ve.insert({dis[u.second.first][u.second.second],{u.second.first,u.second.second}});
                        }
                    }
                }

            }
            int 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].insert({1,{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].insert({1,{l,j}});
                            }
                        }
                        l=i+1;
                         while(l!=x+1){
                            if(grid[l+1][j]=='#'){
                                break;
                            }
                            l++;
                        }
                        if(l!=i+1){
                            adj[i+1][j].insert({1,{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].insert({1,{i,l}});
                        }
                        //left
                        l=j-1;
                        while(l!=0){
                            if(grid[i][l-1]=='#'){
                                break;
                            }
                            l--;
                        }
                        if(l!=j-1&&j!=0){
                            adj[i][j-1].insert({1,{i,l}});
                        }
                    }
                        if(grid[i][j]!='#'){

                            //up
                            int l=i-1;
                            if(grid[l][j]!='#'){
                                     if(l!=0){
                                 while(true){
                                if(grid[l-1][j]=='#'){
                                    break;
                                }
                                l--;

                                }
                            }

                            se[i][j].insert({abs(l-i),{l,j}});
                            }


                            //down
                            l=i+1;
                             if(grid[l][j]!='#'){
                                 while(true){
                                if(grid[l+1][j]=='#'){
                                    break;
                                }
                                l++;
                            }

                            se[i][j].insert({abs(l-i),{l,j}});
                            }

                            //right;
                            l=j+1;
                             if(grid[i][l]!='#'){
                                 while(true){
                                if(grid[i][l+1]=='#'){
                                    break;
                                }
                                l++;
                            }
                            se[i][j].insert({abs(j-l),{i,l}});
                            }

                             //left
                             l=j-1;
                            if(grid[i][l]!='#'){

                                if(l!=0){
                                    while(true){
                                    if(grid[i][l-1]=='#'){
                                        break;
                                    }
                                    l--;
                                    }
                                }
                                se[i][j].insert({abs(j-l),{i,l}});
                            }
                        }
                }
            }
            dijsktra(stx,sty);
            cout<<dis[enx][eny]<<endl;

            }

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:184:31: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
  184 |             cout<<dis[enx][eny]<<endl;
      |                               ^
portals.cpp:184:31: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:183:21: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  183 |             dijsktra(stx,sty);
      |             ~~~~~~~~^~~~~~~~~
portals.cpp:183:21: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30