제출 #1194267

#제출 시각아이디문제언어결과실행 시간메모리
1194267zNatsumiPatkice II (COCI21_patkice2)C++20
110 / 110
241 ms58716 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e3+5, inf = 1e9, mod = 1e9 + 7; const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; #define fi first #define se second #define all(x) x.begin(), x.end() int m, n, a[N][N], f[N][N], trace[N][N]; ii st, ed; int in(){ char x; cin >> x; if(x == '^') return 0; if(x == 'v') return 1; if(x == '<') return 2; if(x == '>') return 3; if(x == '.') return 4; if(x == 'o') return 5; if(x == 'x') return 6; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // #define task "test" // if(fopen(task ".inp", "r")){ // freopen(task ".inp", "r", stdin); // freopen(task ".out", "w", stdout); // } cin >> m >> n; for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++){ a[i][j] = in(); if(a[i][j] == 5) st = {i, j}; if(a[i][j] == 6) ed = {i, j}; f[i][j] = inf; } f[st.fi][st.se] = 0; deque<iii> dq; dq.emplace_back(0, st.fi, st.se); while(dq.size()){ int d, r, c; tie(d, r, c) = dq.front(); dq.pop_front(); if(make_pair(r, c) == ed){ cout << f[r][c] << "\n"; break; } if(d != f[r][c]) continue; for(int i = 0; i < 4; i++){ int nr = r + dr[i], nc = c + dc[i]; if(nr < 1 || nc < 1 || nr > m || nc > n) continue; int cost = (a[r][c] != i && a[r][c] != 5); if(f[nr][nc] > f[r][c] + cost){ if(cost) dq.emplace_back(f[nr][nc] = f[r][c] + cost, nr, nc); else dq.emplace_front(f[nr][nc] = f[r][c] + cost, nr, nc); if(i == 0) trace[nr][nc] = 1; if(i == 1) trace[nr][nc] = 0; if(i == 2) trace[nr][nc] = 3; if(i == 3) trace[nr][nc] = 2; } } } while(1){ int i = trace[ed.fi][ed.se]; int nr = ed.fi + dr[i], nc = ed.se + dc[i]; if(a[nr][nc] == 5) break; if(i == 0) a[nr][nc] = 1; if(i == 1) a[nr][nc] = 0; if(i == 2) a[nr][nc] = 3; if(i == 3) a[nr][nc] = 2; ed = make_pair(nr, nc); } for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++){ if(a[i][j] == 0) cout << '^'; if(a[i][j] == 1) cout << 'v'; if(a[i][j] == 2) cout << '<'; if(a[i][j] == 3) cout << '>'; if(a[i][j] == 4) cout << '.'; if(a[i][j] == 5) cout << 'o'; if(a[i][j] == 6) cout << 'x'; if(j == n) cout << '\n'; } return 0; }

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

Main.cpp: In function 'int in()':
Main.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...