제출 #829672

#제출 시각아이디문제언어결과실행 시간메모리
829672BidoTeima포탈들 (BOI14_portals)C++17
0 / 100
14 ms31980 KiB
#include<bits/stdc++.h> using namespace std; 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>=0&&y>=0&&x<c&&y<c&&grid[x][y]!='#'; } int main() { memset(nearest_wall,0x3f3f3f,sizeof(nearest_wall)); cin>>r>>c; int stx,sty,endx,endy; for(int i = 0; i < r; i++){ for(int j = 0; 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; i++){ for(int j = 0; j < c; 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; i++)sort(walls_x[i].begin(),walls_x[i].end()); for(int i = 0; i < c; 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(check(x+dx[i],y+dy[i])){ q.push({x+dx[i],y+dy[i],d+1}); } } } for(int x = 0; x < r; x++){ for(int y = 0; y < c; y++){ // 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, 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, nearest_wall[x][y])}); } // nearest wall up (>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, x, nearest_wall[x][y])}); } it = upper_bound(walls_y[y].begin(), walls_y[y].end(), x); if(it != walls_y[y].end()){ adj[x][y].push_back({(*it, x, 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)); 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 'int main()':
portals.cpp:64:39: warning: left operand of comma operator has no effect [-Wunused-value]
   64 |                 adj[x][y].push_back({(x, *it, nearest_wall[x][y])});
      |                                       ^
portals.cpp:69:39: warning: left operand of comma operator has no effect [-Wunused-value]
   69 |                 adj[x][y].push_back({(x, *it, nearest_wall[x][y])});
      |                                       ^
portals.cpp:75:64: warning: right operand of comma operator has no effect [-Wunused-value]
   75 |                 adj[x][y].push_back({(*it, x, nearest_wall[x][y])});
      |                                                                ^
portals.cpp:79:64: warning: right operand of comma operator has no effect [-Wunused-value]
   79 |                 adj[x][y].push_back({(*it, x, nearest_wall[x][y])});
      |                                                                ^
portals.cpp:102:26: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |     cout<<dist[endx][endy];
      |                          ^
portals.cpp:102:26: warning: 'endx' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:85:24: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     pq.push({0,stx,sty});
      |                        ^
portals.cpp:85:24: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...