제출 #829740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
829740		BidoTeima	Portals (BOI14_portals)	C++17	0 / 100	16 ms	28052 KiB

portals

#include<bits/stdc++.h>
using namespace std;
#define int short
const int N = 1005;
int nearest_wall[N][N];
vector<vector<int>>adj[N][N];
vector<int>walls_x[N],walls_y[N];
char grid[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int r,c;
bool check(int x, int 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; 
    int stx,sty,endx,endy;
    for(int i = 1; i <= r; i++){
        for(int 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<int>>q;
    for(int i = 0; i <= r + 1; i++){
        grid[i][c+1]='#';
        grid[i][0]='#';
    }
    for(int i = 0; i <= c + 1; i++){
        grid[r+1][i]='#';
        grid[0][i]='#';
    }
    for(int i = 0; i <= r + 1; i++){
        for(int j = 0; j <= c + 1; j++){
            if(grid[i][j]!='#'){
                for(int 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(int i = 0; i <= r+1; i++)sort(walls_x[i].begin(),walls_x[i].end());
    for(int i = 0; i <= c+1; i++)sort(walls_y[i].begin(),walls_y[i].end());
    while(!q.empty()){
        int x = q.front()[0];
        int y = q.front()[1];
        int d = q.front()[2];
        q.pop();
        if(nearest_wall[x][y]<2e6)continue;
        nearest_wall[x][y]=d;
        for(int 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(int x = 0; x <= r+1; x++){
        for(int 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<int>;
    priority_queue<vi,vector<vi>,greater<vi>>pq;
    pq.push({0,stx,sty});
    int dist[N][N];
    memset(dist,0x3f3f3f,sizeof(dist));
    dist[stx][sty]=0;
    while(!pq.empty()){
        int x = pq.top()[1];
        int y = pq.top()[2];
        int d = pq.top()[0];
        pq.pop();
        if(dist[x][y]!=d)continue;
        for(auto&edge:adj[x][y]){
            int 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;
}

컴파일 시 표준 에러 (stderr) 메시지

portals.cpp: In function 'int32_t main()':
portals.cpp:41:47: warning: narrowing conversion of '(((int)i) + ((int)dx[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
   41 |                         adj[i][j].push_back({i+dx[k],j+dy[k],1});
      |                                              ~^~~~~~
portals.cpp:41:47: warning: narrowing conversion of '(((int)i) + ((int)dx[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:41:55: warning: narrowing conversion of '(((int)j) + ((int)dy[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
   41 |                         adj[i][j].push_back({i+dx[k],j+dy[k],1});
      |                                                      ~^~~~~~
portals.cpp:41:55: warning: narrowing conversion of '(((int)j) + ((int)dy[((int)k)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:63:26: warning: narrowing conversion of '(((int)x) + ((int)dx[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
   63 |                 q.push({x+dx[i],y+dy[i],d+1});
      |                         ~^~~~~~
portals.cpp:63:26: warning: narrowing conversion of '(((int)x) + ((int)dx[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:63:34: warning: narrowing conversion of '(((int)y) + ((int)dy[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
   63 |                 q.push({x+dx[i],y+dy[i],d+1});
      |                                 ~^~~~~~
portals.cpp:63:34: warning: narrowing conversion of '(((int)y) + ((int)dy[((int)i)]))' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:63:42: warning: narrowing conversion of '(((int)d) + 1)' from 'int' to 'short int' [-Wnarrowing]
   63 |                 q.push({x+dx[i],y+dy[i],d+1});
      |                                         ~^~
portals.cpp:63:42: warning: narrowing conversion of '(((int)d) + 1)' from 'int' to 'short int' [-Wnarrowing]
portals.cpp:74: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]
   74 |                 adj[x][y].push_back({x, *it + 1, nearest_wall[x][y]});
      |                                         ~~~~^~~
portals.cpp:74: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:79: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]
   79 |                 adj[x][y].push_back({x, *it - 1, nearest_wall[x][y]});
      |                                         ~~~~^~~
portals.cpp:79: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:85: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]
   85 |                 adj[x][y].push_back({*it + 1, y, nearest_wall[x][y]});
      |                                      ~~~~^~~
portals.cpp:85: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:90: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]
   90 |                 adj[x][y].push_back({*it - 1, y, nearest_wall[x][y]});
      |                                      ~~~~^~~
portals.cpp:90: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:96:24: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     pq.push({0,stx,sty});
      |                        ^
portals.cpp:114:22: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     cout<<dist[endx][endy];
      |                      ^~~~
portals.cpp:114:16: warning: 'endx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     cout<<dist[endx][endy];
      |                ^~~~
portals.cpp:96:24: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     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