제출 #943243

#제출 시각아이디문제언어결과실행 시간메모리
943243salmon포탈들 (BOI14_portals)C++14
0 / 100
3 ms12888 KiB
#include <bits/stdc++.h> using namespace std; int R; int C; int x,y; int gx,gy; int sx,sy; char c; int lst[1100][1100]; int nextr[1100][1100]; int nextc[1100][1100]; int prevr[1100][1100]; int prevc[1100][1100]; int dw[1100][1100]; int d[1100][1100]; priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq; queue<vector<int>> q; vector<pair<int,int>> bah = {{0,-1},{0,1},{1,0},{-1,0}}; bool valid(int i, int j){ if(i >= 0 && i < R && 0 <= j && j < C) return true; return false; } int main(){ scanf(" %d",&R); scanf(" %d",&C); for(int i = 0; i < R; i++){ for(int j = 0; j < C; j++){ scanf(" %c",&c); if(c == '#'){ lst[i][j] = 1; } else{ lst[i][j] = 0; } if(c == 'C'){ gx = i; gy = j; } if(c == 'S'){ sx = i; sy = j; } d[i][j] = -1; dw[i][j] = -1; } } for(int i = 0; i < R; i++){ vector<int> s; for(int j = 0; j < C; j++){ while(!s.empty() && lst[i][j] == 1){ nextr[i][s.back()] = j; s.pop_back(); } s.push_back(j); } while(!s.empty()){ nextr[i][s.back()] = C; s.pop_back(); } } for(int j = 0; j < C; j++){ vector<int> s; for(int i = 0; i < R; i++){ while(!s.empty() && lst[i][j] == 1){ nextc[s.back()][j] = i; s.pop_back(); } s.push_back(i); } while(!s.empty()){ nextc[s.back()][j] = R; s.pop_back(); } } for(int i = 0; i < R; i++){ vector<int> s; for(int j = C - 1; j >= 0; j--){ while(!s.empty() && lst[i][j] == 1){ prevr[i][s.back()] = j; s.pop_back(); } s.push_back(j); } while(!s.empty()){ prevr[i][s.back()] = -1; s.pop_back(); } } for(int j = 0; j < C; j++){ vector<int> s; for(int i = R - 1; i >= 0; i--){ while(!s.empty() && lst[i][j] == 1){ prevc[s.back()][j] = i; s.pop_back(); } s.push_back(i); } while(!s.empty()){ prevc[s.back()][j] = -1; s.pop_back(); } } for(int i = 0; i < R; i++){ for(int j = 0; j < C; j++){ if(lst[i][j] == 1) q.push({i,j,0}); } } for(int i = 0; i < R; i++){ q.push({i,0,1}); q.push({i,C-1,1}); } for(int i = 0; i < C; i++){ q.push({0,i,1}); q.push({R-1,i,1}); } while(!q.empty()){ vector<int> v = q.front(); q.pop(); int i = v[0]; int j = v[1]; if(dw[i][j] != -1) continue; dw[i][j] = v[2]; for(pair<int,int> ii : bah){ int ni = ii.first + i; int nj = ii.second + j; if(valid(ni,nj) && dw[i][j] == -1 && lst[i][j] != 1){ q.push({ni,nj,v[2] + 1}); } } } pq.push({0,sx,sy}); //pq.push({0,sx,sy,false}); while(!pq.empty()){ vector<int> v = pq.top(); pq.pop(); int i = v[1]; int j = v[2]; int de = v[0]; if(d[i][j] != -1) continue; if(lst[i][j] == 1) continue; d[i][j] = de; for(pair<int,int> ii : bah){ int ni = ii.first + i; int nj = ii.second + j; if(valid(ni,nj) && lst[ni][nj] != 1 && d[ni][nj] == -1){ pq.push({de+1,ni,nj}); } } if(d[i][prevr[i][j] + 1] == -1) pq.push({de + dw[i][j],i,prevr[i][j] + 1}); if(d[i][nextr[i][j] - 1] == -1) pq.push({de + dw[i][j],i,nextr[i][j] - 1}); if(d[prevc[i][j] + 1][j] == -1) pq.push({de + dw[i][j],prevc[i][j] + 1,j}); if(d[nextc[i][j] - 1][j] == -1) pq.push({de + dw[i][j],nextc[i][j] - 1,j}); } /*for(int i = 0; i < R; i++){ for(int j = 0; j < C; j++){ printf("%d ",dw[i][j]); } printf("\n"); }*/ printf("%d",d[gx][gy]); } /* 5 4 G#.# .#.# ...# S..# .... */

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

portals.cpp: In function 'int main()':
portals.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf(" %d",&R);
      |     ~~~~~^~~~~~~~~~
portals.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf(" %d",&C);
      |     ~~~~~^~~~~~~~~~
portals.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |             scanf(" %c",&c);
      |             ~~~~~^~~~~~~~~~
#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...