Submission #466810

#	Time	Username	Problem	Language	Result	Execution time	Memory
466810		AnasBenMoussa	Portals (BOI14_portals)	C++14	0 / 100	30 ms	48372 KiB

portals

#include <bits/stdc++.h>

typedef double db ;
using namespace std;
#define all(x) begin(x), end(x)
#define pb push_back
#define int long long
#define doub(k) printf("%.1lf\n", k) // setprecision(5)
typedef pair<int ,int > pll;typedef map<int , int > mll;typedef vector<int > vll;typedef vector<pll>vpll;
 typedef set<int > sll;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};
const int dr[8] = {1,1,0,-1,-1,-1, 0, 1}, dc[8] = {0,1,1, 1, 0,-1,-1,-1};
//vector<char>v{'R','B','G'};
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
char grid[1000][1000];pll star,en;int vis[1000][1000];
int dis[10000][10000];
set<pair<int,int>>adj[1000][1000];int x,y;
void  solve(int n ,int j){

        for(int i=0;i<=1000;i++){
            if(grid[n][j-i]!='#'&&grid[n][j-i-1]=='#'){
                if(grid[n][j-i]=='#'){
                    continue;
                }
                 if(n<=0||j-i<=0||n>x||j-i>y){
                    continue;
                }
                adj[n][j-i].insert({n,j});
                adj[n][j].insert({n,j-i});
                break;
            }
        }

        for(int i=0;i<=1000;i++){
            if(grid[n+i][j]!='#'&&grid[n+i+1][j]=='#'){
                    if(grid[n+i][j]=='#'){
                    continue;
                }
                 if(n+i<=0||j<=0||n+i>x||j>y){
                    continue;
                }
                adj[n+i][j].insert({n,j});
                adj[n][j].insert({n+i,j});
                break;

        }

        for(int i=0;i<=10000;i++){
                if(grid[n-i][j]=='#'){
                    continue;
                }
            if(grid[n-i][j]!='#'&&grid[n-i-1][j]=='#'){
                if(n-i<=0||j<=0||n-i>x||j>y){
                    continue;
                }
                 adj[n-i][j].insert({n,j});
                adj[n][j].insert({n-i,j});
                break;
            }
        }
          for(int i=0;i<=10000;i++){
              if(grid[n][j+i]=='#'){
                    continue;
                }
            if(grid[n][j+i]!='#'&&grid[n][j+i+1]=='#'){
                 if(n<=0||j+i<=0||n>x||j+i>y){
                    continue;
                }

                  adj[n][j+i].insert({n,j});
                adj[n][j].insert({n,j+i});
                break;
            }
        }
    for(int r=0;r<4;r++){
        if(n+nx[r]<=0||n+nx[r]>x||j+ny[r]<=0||j+ny[r]>y){
            continue;
        }
        if(grid[n+nx[r]][j+ny[r]]=='#'){
            continue;
        }
       adj[n][j].insert({n+nx[r],j+ny[r]});
       adj[n+nx[r]][j+ny[r]].insert({n,j});


}
}}
void bfs(int t,int tt){
    queue<pair<int,int>>q;
    q.push({t,tt});
    dis[t][tt]=0;
    while(!q.empty()){

        int  r=q.front().first;
        int c=q.front().second;
    //cout<<r<<" "<<c<<endl;
      //  cout<<dis[r][c];
        q.pop();

        for(auto u:adj[r][c]){
            if(vis[u.first][u.second]){
                continue;
            }
            vis[u.first][u.second]=1;
            dis[u.first][u.second]=dis[r][c]+1;
            q.push({u.first,u.second});
        }
    }
}
    int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin>>x;
    cin>>y;
    memset(grid,'#',sizeof(grid));
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            char t;cin>>t;
            if(t=='S'){
                star={i,j};
            }
            if(t=='C'){
                en={i,j};
            }
            grid[i][j]=t;
        }
    }
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            if(grid[i][j]=='#'){
                continue;
            }
            solve(i,j);
        }
    }
    /*for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            cout<<i<<" "<<j<<"<<  ";
            for(auto u:adj[i][j]){
                cout<<u.first<<" "<<u.second<<"[";
            }
            cout<<endl;
        }
    }*/

    bfs(star.first,star.second);
   // for(int i=1;i<=x;i++){
     //   for(int j=1;j<=y;j++){
      //      cout<<i<<" "<<j<<"    "<<dis[i][j]<<endl;
       // }
    //}
    cout<<dis[en.first][en.second]<<endl;
    return 0;
}

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