제출 #943303

#제출 시각아이디문제언어결과실행 시간메모리
943303itslq포탈들 (BOI14_portals)C++17
0 / 100
3 ms8668 KiB
#include <bits/stdc++.h> using namespace std; int R, C; const pair<int, int> dirs[4] = {make_pair(0, 1), make_pair(0, -1), make_pair(1, 0), make_pair(-1, 0)}; priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> tocheck; //queue<pair<pair<int, int>, int>> tocheck; bool visited[1000][1000], grid[1000][1000]; int LA[1000][1000], RA[1000][1000], UA[1000][1000], DA[1000][1000]; void add(int x, int y, int n) { //cout << R << " " << C << endl; // cout << x << " " << y << " " << n << endl; // cout << grid[x][y] << " " << visited[x][y] << endl; if (x < 0 || y < 0 || x >= R || y >= C || grid[x][y] || visited[x][y]) return; tocheck.emplace(n + 1, make_pair(x, y)); //cout << x << " " << y << " " << n << endl; //cout << x << " " << y << " " << n + 1 << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int P = 0, si, sj, ei, ej, ni, nj, ci, cj, dist; cin >> R >> C; string row; for (int i = 0; i < R; i++) { memset(visited[i], 0, sizeof(visited[i])); P = 0; cin >> row; for (int j = 0; j < C; j++) { LA[i][j] = P; switch (row[j]) { case '.': grid[i][j] = 0; break; case '#': grid[i][j] = 1; P = j + 1; break; case 'S': si = i; sj = j; grid[i][j] = 0; break; case 'C': ei = i; ej = j; grid[i][j] = 0; break; } } P = C - 1; for (int j = C - 1; j >= 0; j--) { RA[i][j] = P; if (grid[i][j]) P = j - 1; } } for (int j = 0; j < C; j++) { P = 0; for (int i = 0; i < R; i++) { UA[i][j] = P; if (grid[i][j]) P = i + 1; } P = R - 1; for (int i = R - 1; i >= 0; i--) { DA[i][j] = P; if (grid[i][j]) P = i - 1; } } pair<int, pair<int, int>> curr; add(si, sj, -1); //return 0; while (true) { curr = tocheck.top(); tocheck.pop(); ci = curr.second.first; cj = curr.second.second; //cout << ci << " " << cj << " " << curr.first << endl; if (visited[ci][cj]) continue; visited[ci][cj] = 1; //cout << ci << " " << cj << " " << curr.second << endl; if (ci == ei && cj == ej) { cout << curr.first; return 0; } for (pair<int, int> d: dirs) add(ci + d.first, cj + d.second, curr.first); if (cj == 0 || cj == C - 1 || ci == 0 || ci == R - 1) dist = 0; else dist = min(min(abs(LA[ci][cj] - cj), abs(RA[ci][cj] - cj)), min(abs(UA[ci][cj] - ci), abs(DA[ci][cj] - ci))) - 1; add(ci, LA[ci][cj], curr.first + dist); add(ci, RA[ci][cj], curr.first + dist); add(UA[ci][cj], cj, curr.first + dist); add(DA[ci][cj], cj, curr.first + dist); } }

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

portals.cpp: In function 'int main()':
portals.cpp:25:32: warning: unused variable 'ni' [-Wunused-variable]
   25 |     int P = 0, si, sj, ei, ej, ni, nj, ci, cj, dist;
      |                                ^~
portals.cpp:25:36: warning: unused variable 'nj' [-Wunused-variable]
   25 |     int P = 0, si, sj, ei, ej, ni, nj, ci, cj, dist;
      |                                    ^~
portals.cpp:97:28: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |         if (ci == ei && cj == ej) {
      |                         ~~~^~~~~
portals.cpp:97:16: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |         if (ci == ei && cj == ej) {
      |             ~~~^~~~~
portals.cpp:80:8: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     add(si, sj, -1);
      |     ~~~^~~~~~~~~~~~
portals.cpp:80:8: warning: 'si' 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...