oj.uz

Submission #375747

# Submission time Handle Problem Language Result Execution time Memory
375747 2021-03-09T23:53:07 Z Ahmad_Hasan Portals (BOI14_portals) C++17
20 / 100
 18 ms 18688 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16108 KB Output is correct
2 Correct 8 ms 16108 KB Output is correct
3 Correct 8 ms 16108 KB Output is correct
4 Correct 8 ms 16108 KB Output is correct
5 Correct 8 ms 16108 KB Output is correct
6 Correct 8 ms 16108 KB Output is correct
7 Correct 8 ms 16236 KB Output is correct
8 Correct 8 ms 16108 KB Output is correct
9 Correct 8 ms 16108 KB Output is correct
10 Incorrect 8 ms 16180 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16108 KB Output is correct
2 Correct 8 ms 16108 KB Output is correct
3 Correct 9 ms 16108 KB Output is correct
4 Correct 11 ms 16108 KB Output is correct
5 Correct 9 ms 16108 KB Output is correct
6 Correct 8 ms 16108 KB Output is correct
7 Correct 8 ms 16108 KB Output is correct
8 Correct 8 ms 16108 KB Output is correct
9 Correct 9 ms 16364 KB Output is correct
10 Incorrect 9 ms 16364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16108 KB Output is correct
2 Correct 8 ms 16108 KB Output is correct
3 Correct 8 ms 16108 KB Output is correct
4 Correct 8 ms 16108 KB Output is correct
5 Correct 16 ms 18412 KB Output is correct
6 Correct 18 ms 18560 KB Output is correct
7 Correct 18 ms 18688 KB Output is correct
8 Correct 15 ms 18412 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16108 KB Output is correct
2 Correct 9 ms 16108 KB Output is correct
3 Correct 8 ms 16108 KB Output is correct
4 Correct 8 ms 16108 KB Output is correct
5 Correct 8 ms 16108 KB Output is correct
6 Correct 8 ms 16108 KB Output is correct
7 Correct 8 ms 16108 KB Output is correct
8 Correct 8 ms 16108 KB Output is correct
9 Correct 9 ms 16364 KB Output is correct
10 Incorrect 9 ms 16364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16108 KB Output is correct
2 Correct 9 ms 16108 KB Output is correct
3 Correct 8 ms 16108 KB Output is correct
4 Correct 9 ms 16108 KB Output is correct
5 Correct 8 ms 16108 KB Output is correct
6 Correct 8 ms 16108 KB Output is correct
7 Correct 8 ms 16108 KB Output is correct
8 Correct 8 ms 16108 KB Output is correct
9 Correct 9 ms 16364 KB Output is correct
10 Incorrect 9 ms 16364 KB Output isn't correct
11 Halted 0 ms 0 KB -