제출 #829775

#제출 시각아이디문제언어결과실행 시간메모리
829775BidoTeima포탈들 (BOI14_portals)C++17
70 / 100
321 ms262144 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>=1&&y>=1&&x<=r&&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 = 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 a3 = tuple<int,short,short>; priority_queue<a3,vector<a3>,greater<a3>>pq; pq.push({0,stx,sty}); int dist[N][N]; memset(dist,0x3f3f3f,sizeof(dist)); dist[stx][sty]=0; while(!pq.empty()){ short x = get<1>(pq.top()); short y = get<2>(pq.top()); int d = get<0>(pq.top()); 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; }

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

portals.cpp: In function 'int main()':
portals.cpp:98:19: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     dist[stx][sty]=0;
      |     ~~~~~~~~~~~~~~^~
portals.cpp:113:26: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     cout<<dist[endx][endy];
      |                          ^
portals.cpp:113:26: warning: 'endx' 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...