Submission #375747

#	Time	Username	Problem	Language	Result	Execution time	Memory
375747		Ahmad_Hasan	Portals (BOI14_portals)	C++17	20 / 100	18 ms	18688 KiB

portals

#include <bits/stdc++.h>
/**
     ||||||||||       |||||     |||||    ||||||||||
    |||||||||||||     |||||     |||||  |||||
   ||||     ||||||    |||||     |||||  |||||
  |||||||||||||||||   |||||||||||||||    ||||||||||
 |||||||||||||||||||  |||||||||||||||           |||||
 |||||         |||||  |||||     |||||           |||||
 |||||         |||||  |||||     |||||    ||||||||||
AHMED;HASSAN;SAEED;
*/


///#define int long long
using namespace std;

int dirs[4][1005][1005];

vector<vector<int> >adj;
int s,c;
int n,m;

int bfs(){
    queue<int>q;
    vector<int>vis(n*m+5),d(n*m+5);

    q.push(s);
    int dis=0;

    while(!q.empty()){
        int sz=q.size();
        int f=0;
        while(sz--){
            int cr=q.front();   q.pop();
            if(vis[cr])continue;
            vis[cr]=1;
            d[cr]=dis;
            /**cout<<cr/n<<','<<cr%n<<'='<<d[cr];

            cout<<'\n';*/
            if(cr==c){
                f=1;
                break;
            }

            for(int i=0;i<adj[cr].size();i++){
                if(!vis[adj[cr][i]]){
                    q.push(adj[cr][i]);
                }
            }
        }
        if(f)break;

        dis++;
    }
/**
    for(int i=0;i<n*m;i++){
        cout<<i/n<<','<<i%n<<'='<<d[i];

        cout<<'\n';
    }
*/
    return dis;
}


int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);


    cin>>n>>m;

    adj.resize(n*m+5);

    vector<string>vs(n);
    for(int i=0;i<n;i++)
        cin>>vs[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vs[i][j]=='S')
                s=i*m+j;
            if(vs[i][j]=='C')
                c=i*m+j;
            if(j+1<m&&vs[i][j]!='#'&&vs[i][j+1]!='#'){
                adj[i*m+j].push_back(i*m+j+1);
                adj[i*m+j+1].push_back(i*m+j);
            }
            if(i+1<n&&vs[i][j]!='#'&&vs[i+1][j]!='#'){
                adj[(i)*m+j].push_back((i+1)*m+j);
                adj[(i+1)*m+j].push_back(i*m+j);
            }
        }
    }

    memset(dirs,-1,sizeof(dirs));

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vs[i][j]=='#'){
                dirs[0][i][j]=-1;
                dirs[1][i][j]=-1;
            }else{
                if(j-1>=0&&dirs[0][i][j-1]!=-1){
                    dirs[0][i][j]=dirs[0][i][j-1];
                }else{
                    dirs[0][i][j]=(i*m)+j;
                }
                if(i-1>=0&&dirs[1][i-1][j]!=-1){
                    dirs[1][i][j]=dirs[1][i-1][j];
                }else{
                    dirs[1][i][j]=(i*m)+j;
                }

            }
        }
    }

    for(int i=n-1;i>=0;i--){
        for(int j=m-1;j>=0;j--){
            if(vs[i][j]=='#'){
                dirs[2][i][j]=-1;
                dirs[3][i][j]=-1;
            }else{
                if(j+1<m&&dirs[2][i][j+1]!=-1){
                    dirs[2][i][j]=dirs[2][i][j+1];
                }else{
                    dirs[2][i][j]=(i*m)+j;
                }
                if(i+1<n&&dirs[3][i+1][j]!=-1){
                    dirs[3][i][j]=dirs[3][i+1][j];
                }else{
                    dirs[3][i][j]=(i*m)+j;
                }

            }
        }
    }
/**
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<i*m+j<<' ';
        }
        cout<<'\n';
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<dirs[0][i][j]<<' ';
        }
        cout<<'\n';
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<dirs[1][i][j]<<' ';
        }
        cout<<'\n';
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<dirs[1][i][j]<<' ';
        }
        cout<<'\n';
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<dirs[3][i][j]<<' ';
        }
        cout<<'\n';
    }
*/
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int f=0;
            for(int k=0;k<4;k++){
                if(dirs[k][i][j]==i*m+j){
                    f=k+1;
                    break;
                }
            }
            ///cout<<f<<' ';
            for(int k=0;k<4&&f;k++){
                if(dirs[k][i][j]!=-1&&dirs[k][i][j]!=i*m+j){
                    adj[i*m+j].push_back(dirs[k][i][j]);
                    ///adj[dirs[k][i][j]].push_back(i*m+j);
                }
            }
        }
        ///cout<<'\n';
    }
/**


    for(int i=0;i<n*m;i++){
        cout<<i/n<<','<<i%n<<'=';
        for(int j=0;j<adj[i].size();j++)
            cout<<adj[i][j]<<' ';
        cout<<'\n';
    }
*/


    cout<<bfs()<<'\n';
    return 0;
}



/**
1
8 2
abczzzzz

*/

Compilation message (stderr)

portals.cpp: In function 'int bfs()':
portals.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int i=0;i<adj[cr].size();i++){
      |                         ~^~~~~~~~~~~~~~~

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