제출 #860404

#제출 시각아이디문제언어결과실행 시간메모리
860404serifefedartarPatkice II (COCI21_patkice2)C++17
15 / 110
710 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9 + 7; const ll LOGN = 18; const ll MAXN = 1e5 + 100; vector<pair<int,pair<int,int>>> graph[2005][2005], rev[2005][2005]; int dist[2005][2005], vis[2005][2005]; vector<string> grid; pair<int,int> s, e; void change(int row, int col, int nrow, int ncol) { if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col) return ; if (nrow > row) grid[row][col] = 'v'; else if (nrow < row) grid[row][col] = '^'; else if (ncol < col) grid[row][col] = '<'; else grid[row][col] = '>'; } void dfs(int row, int col, int target) { vis[row][col] = true; for (auto u : rev[row][col]) { int w = u.f; int nrow = u.s.f; int ncol = u.s.s; if (vis[nrow][ncol]) continue; if (dist[nrow][ncol] + w == target) { change(nrow, ncol, row, col); dfs(nrow, ncol, target - w); return ; } } } int r, c; bool check(int row, int col) { if (row >= 0 && col >= 0 && r > row && c > col) return true; return false; } int main() { fast cin >> r >> c; for (int i = 0; i < 2005; i++) { for (int j = 0; j < 2005; j++) dist[i][j] = 1e8; } grid = vector<string>(r); for (int i = 0; i < r; i++) cin >> grid[i]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (grid[i][j] == '>') { if (check(i, j+1)) { graph[i][j].push_back({0, {i, j+1}}); rev[i][j+1].push_back({0, {i, j}}); } if (check(i+1, j)) { graph[i][j].push_back({1, {i+1, j}}); rev[i+1][j].push_back({1, {i, j}}); } if (check(i, j-1)) { graph[i][j].push_back({1, {i, j-1}}); rev[i][j-1].push_back({1, {i, j}}); } if (check(i-1, j)) { graph[i][j].push_back({1, {i-1, j}}); rev[i-1][j].push_back({1, {i, j}}); } } else if (grid[i][j] == '<') { if (check(i, j+1)) { graph[i][j].push_back({1, {i, j+1}}); rev[i][j+1].push_back({1, {i, j}}); } if (check(i+1, j)) { graph[i][j].push_back({1, {i+1, j}}); rev[i+1][j].push_back({1, {i, j}}); } if (check(i, j-1)) { graph[i][j].push_back({0, {i, j-1}}); rev[i][j-1].push_back({0, {i, j}}); } if (check(i-1, j)) { graph[i][j].push_back({1, {i-1, j}}); rev[i-1][j].push_back({1, {i, j}}); } } else if (grid[i][j] == 'v') { if (check(i, j+1)) { graph[i][j].push_back({1, {i, j+1}}); rev[i][j+1].push_back({1, {i, j}}); } if (check(i+1, j)) { graph[i][j].push_back({0, {i+1, j}}); rev[i+1][j].push_back({0, {i, j}}); } if (check(i, j-1)) { graph[i][j].push_back({1, {i, j-1}}); rev[i][j-1].push_back({1, {i, j}}); } if (check(i-1, j)) { graph[i][j].push_back({1, {i-1, j}}); rev[i-1][j].push_back({1, {i, j}}); } } else if (grid[i][j] == '^') { if (check(i, j+1)) { graph[i][j].push_back({1, {i, j+1}}); rev[i][j+1].push_back({1, {i, j}}); } if (check(i+1, j)) { graph[i][j].push_back({1, {i+1, j}}); rev[i+1][j].push_back({1, {i, j}}); } if (check(i, j-1)) { graph[i][j].push_back({1, {i, j-1}}); rev[i][j-1].push_back({1, {i, j}}); } if (check(i-1, j)) { graph[i][j].push_back({0, {i-1, j}}); rev[i-1][j].push_back({0, {i, j}}); } } else if (grid[i][j] == '.') { if (check(i, j+1)) { graph[i][j].push_back({1, {i, j+1}}); rev[i][j+1].push_back({1, {i, j}}); } if (check(i+1, j)) { graph[i][j].push_back({1, {i+1, j}}); rev[i+1][j].push_back({1, {i, j}}); } if (check(i, j-1)) { graph[i][j].push_back({1, {i, j-1}}); rev[i][j-1].push_back({1, {i, j}}); } if (check(i-1, j)) { graph[i][j].push_back({1, {i-1, j}}); rev[i-1][j].push_back({1, {i, j}}); } } else if (grid[i][j] == 'o') { s = {i, j}; if (check(i, j+1)) { graph[i][j].push_back({0, {i, j+1}}); rev[i][j+1].push_back({0, {i, j}}); } if (check(i+1, j)) { graph[i][j].push_back({0, {i+1, j}}); rev[i+1][j].push_back({0, {i, j}}); } if (check(i, j-1)) { graph[i][j].push_back({0, {i, j-1}}); rev[i][j-1].push_back({0, {i, j}}); } if (check(i-1, j)) { graph[i][j].push_back({0, {i-1, j}}); rev[i-1][j].push_back({0, {i, j}}); } } else e = {i, j}; } } deque<pair<int,int>> dq; dq.push_back(s); dist[s.f][s.s] = 0; while (!dq.empty()) { int row = dq.front().f; int col = dq.front().s; dq.pop_front(); for (auto u : graph[row][col]) { int w = u.f; int nrow = u.s.f; int ncol = u.s.s; if (dist[nrow][ncol] > w + dist[row][col]) { dist[nrow][ncol] = w + dist[row][col]; if (w == 1) dq.push_back({nrow, ncol}); else dq.push_front({nrow, ncol}); } } } cout << dist[e.f][e.s] << "\n"; memset(vis, 0, sizeof(vis)); dfs(e.f, e.s, dist[e.f][e.s]); grid[s.f][s.s] = 'o'; for (int i = 0; i < r; i++) cout << grid[i] << "\n"; }

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

Main.cpp: In function 'void change(int, int, int, int)':
Main.cpp:17:46: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |     if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col)
      |                               ~~~~~~~~~~~~~~~^~~~~~
Main.cpp:17:71: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |     if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col)
      |                                                        ~~~~~~~~~~~~~~~^~~~~~
Main.cpp:17:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   17 |     if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col)
      |     ^~
Main.cpp:20:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |  if (nrow > row)
      |  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...