Submission #829757

#	Time	Username	Problem	Language	Result	Execution time	Memory
829757		BidoTeima	Portals (BOI14_portals)	C++17	0 / 100	19 ms	28036 KiB

portals

#include<bits/stdc++.h>
using namespace std; 
const int N = 1005;
short nearest_wall[N][N];
vector<vector<short>>adj[N][N];
vector<short>walls_x[N],walls_y[N];
char grid[N][N];
short dx[4]={0,0,-1,1};
short dy[4]={-1,1,0,0};
short r,c;
bool check(short x, short y){
    return x>=1&&y>=1&&x<=r&&y<=c&&grid[x][y]!='#';
}
int32_t main()
{ 
    memset(nearest_wall,0x3f3f3f,sizeof(nearest_wall));
    cin>>r>>c; 
    short stx,sty,endx,endy;
    for(short i = 1; i <= r; i++){
        for(short j = 1; j <= c; j++){
            cin>>grid[i][j];
            if(grid[i][j]=='S')stx=i,sty=j;
            if(grid[i][j]=='C')endx=i,endy=j;
        }
    }
    queue<vector<short>>q;
    for(short i = 0; i <= r + 1; i++){
        grid[i][c+1]='#';
        grid[i][0]='#';
    }
    for(short i = 0; i <= c + 1; i++){
        grid[r+1][i]='#';
        grid[0][i]='#';
    }
    for(short i = 0; i <= r + 1; i++){
        for(short j = 0; j <= c + 1; j++){
            if(grid[i][j]!='#'){
                for(short k = 0; k < 4; k++){
                    if(check(i+dx[k],j+dy[k])){
                        adj[i][j].push_back({i+dx[k],j+dy[k],1});
                    }
                }
            }
            else{
                walls_x[i].push_back(j);
                walls_y[j].push_back(i);
                q.push({i, j, 0}); 
            }
        }
    }
    for(short i = 0; i <= r+1; i++)sort(walls_x[i].begin(),walls_x[i].end());
    for(short i = 0; i <= c+1; i++)sort(walls_y[i].begin(),walls_y[i].end());
    while(!q.empty()){
        short x = q.front()[0];
        short y = q.front()[1];
        short d = q.front()[2];
        q.pop();
        if(nearest_wall[x][y]<2e6)continue;
        nearest_wall[x][y]=d;
        for(short i = 0; i < 4; i++){
            if(x+dx[i]>=0&&x+dx[i]<=r+1&&y+dy[i]>=0&&y+dy[i]<=c+1){
                q.push({x+dx[i],y+dy[i],d+1});
            }
        }
    }
    for(short x = 0; x <= r+1; x++){
        for(short y = 0; y <= c+1; y++){ 
            if(grid[x][y]=='#')continue;
            // nearest wall to the left (<y)
            auto it = lower_bound(walls_x[x].begin(), walls_x[x].end(), y);
            if(it != walls_x[x].begin()){
                it = prev(it);
                adj[x][y].push_back({x, *it + 1, nearest_wall[x][y]});
            }
            // nearest wall to the right (>y)
            it = upper_bound(walls_x[x].begin(), walls_x[x].end(), y);
            if(it != walls_x[x].end()){
                adj[x][y].push_back({x, *it - 1, nearest_wall[x][y]});
            }
            // nearest wall down (<x)
            it = lower_bound(walls_y[y].begin(), walls_y[y].end(), x);
            if(it != walls_y[y].begin()){
                it = prev(it);
                adj[x][y].push_back({*it + 1, y, nearest_wall[x][y]});
            }
            // nearest wall up (>x)
            it = upper_bound(walls_y[y].begin(), walls_y[y].end(), x);
            if(it != walls_y[y].end()){
                adj[x][y].push_back({*it - 1, y, nearest_wall[x][y]});
            }
        }
    }
    using vi = vector<short>;
    priority_queue<vi,vector<vi>,greater<vi>>pq;
    pq.push({0,stx,sty});
    short dist[N][N];
    memset(dist,0x3f3f3f,sizeof(dist));
    dist[stx][sty]=0;
    while(!pq.empty()){
        short x = pq.top()[1];
        short y = pq.top()[2];
        short d = pq.top()[0];
        pq.pop();
        if(dist[x][y]!=d)continue;
        for(auto&edge:adj[x][y]){
            short nx=edge[0],ny=edge[1];
            if(d + edge[2] < dist[nx][ny]){
                dist[nx][ny]=d+edge[2];
                pq.push({dist[nx][ny],nx,ny});
            }
        }
    }
    cout<<dist[endx][endy];
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int32_t main()':
portals.cpp:40:47: warning: narrowing conversion of '(((int)i) + ((int)dx[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
   40 |                         adj[i][j].push_back({i+dx[k],j+dy[k],1});
      |                                              ~^~~~~~
portals.cpp:40:47: warning: narrowing conversion of '(((int)i) + ((int)dx[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:40:55: warning: narrowing conversion of '(((int)j) + ((int)dy[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
   40 |                         adj[i][j].push_back({i+dx[k],j+dy[k],1});
      |                                                      ~^~~~~~
portals.cpp:40:55: warning: narrowing conversion of '(((int)j) + ((int)dy[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:62:26: warning: narrowing conversion of '(((int)x) + ((int)dx[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
   62 |                 q.push({x+dx[i],y+dy[i],d+1});
      |                         ~^~~~~~
portals.cpp:62:26: warning: narrowing conversion of '(((int)x) + ((int)dx[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:62:34: warning: narrowing conversion of '(((int)y) + ((int)dy[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
   62 |                 q.push({x+dx[i],y+dy[i],d+1});
      |                                 ~^~~~~~
portals.cpp:62:34: warning: narrowing conversion of '(((int)y) + ((int)dy[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:62:42: warning: narrowing conversion of '(((int)d) + 1)' from 'int' to 'short int' [-Wnarrowing]
   62 |                 q.push({x+dx[i],y+dy[i],d+1});
      |                                         ~^~
portals.cpp:62:42: warning: narrowing conversion of '(((int)d) + 1)' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:73:45: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) + 1)' from 'int' to 'short int' [-Wnarrowing]
   73 |                 adj[x][y].push_back({x, *it + 1, nearest_wall[x][y]});
      |                                         ~~~~^~~
portals.cpp:73:45: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) + 1)' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:78:45: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) - 1)' from 'int' to 'short int' [-Wnarrowing]
   78 |                 adj[x][y].push_back({x, *it - 1, nearest_wall[x][y]});
      |                                         ~~~~^~~
portals.cpp:78:45: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) - 1)' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:84:42: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) + 1)' from 'int' to 'short int' [-Wnarrowing]
   84 |                 adj[x][y].push_back({*it + 1, y, nearest_wall[x][y]});
      |                                      ~~~~^~~
portals.cpp:84:42: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) + 1)' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:89:42: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) - 1)' from 'int' to 'short int' [-Wnarrowing]
   89 |                 adj[x][y].push_back({*it - 1, y, nearest_wall[x][y]});
      |                                      ~~~~^~~
portals.cpp:89:42: warning: narrowing conversion of '(((int)it.__gnu_cxx::__normal_iterator<short int*, std::vector<short int> >::operator*()) - 1)' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:95:24: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     pq.push({0,stx,sty});
      |                        ^
portals.cpp:113:22: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     cout<<dist[endx][endy];
      |                      ^~~~
portals.cpp:113:16: warning: 'endx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     cout<<dist[endx][endy];
      |                ^~~~
portals.cpp:95:24: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     pq.push({0,stx,sty});
      |                        ^

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