#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |