#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef short int si;
typedef pair<si, si> pii;
typedef tuple<si, si, si> tiii;
typedef tuple<si, si, si, si> tiiii;
const int N = 505, dir = 4, R = 9, inf = 10e8;
pii nxt[N][N][dir];
int cost[R][N][N], dp[R][R][N][N];
char grid[N][N];
int n, w, h;
int dr[dir] = {1, 0, - 1, 0};
int dc[dir] = {0, 1, 0, - 1}; //down, right, up, left
queue<tiiii> q3[300 * N];
int main(){
cin >> n >> w >> h;
w += 2; h += 2;
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++){
grid[i][j] = 'x';
for(int k = 0; k < dir; k++)
nxt[i][j][k] = {- 1, - 1};
for(int k = 0; k < n; k++)
cost[k][i][j] = - 1;
for(int k = 0; k < n; k++)
for(int l = 0; l < n; l++)
dp[k][l][i][j] = inf;
}
queue<tiii> q0, q1;
for(int i = 1; i < h - 1; i++)
for(int j = 1; j < w - 1; j++){
cin >> grid[i][j];
if(grid[i][j] >= '1' && grid[i][j] <= '9'){
cost[grid[i][j] - '1'][i][j] = 0;
q1.push({grid[i][j] - '1', i, j});
}
}
for(int i = 1; i < h - 1; i++)
for(int j = 1; j < w - 1; j++)
for(int k = 0; k < dir; k++)
if(grid[i][j] != 'x' && grid[i + dr[k]][j + dc[k]] == 'x'){
q0.push({i, j, k});
nxt[i][j][k] = {i, j};
}
while(!q0.empty()){
tiii curr = q0.front();
q0.pop();
int d = get<2>(curr), id, mov;
pii pos = {get<0>(curr), get<1>(curr)};
if(grid[pos.fi][pos.se] == 'A') mov = (d + 1) % 4, id = (d + 3) % 4;
else if(grid[pos.fi][pos.se] == 'C') mov = (d + 3) % 4, id = (d + 1) % 4;
else mov = (d + 2) % 4, id = d;
if(grid[pos.fi + dr[mov]][pos.se + dc[mov]] == 'x') continue;
nxt[pos.fi + dr[mov]][pos.se + dc[mov]][id] = nxt[pos.fi][pos.se][d];
q0.push({pos.fi + dr[mov], pos.se + dc[mov], id});
}
while(!q1.empty()){
tiii curr = q1.front();
q1.pop();
int r = get<0>(curr);
pii pos = {get<1>(curr), get<2>(curr)};
dp[r][r][pos.fi][pos.se] = cost[r][pos.fi][pos.se];
q3[cost[r][pos.fi][pos.se]].push({r, r, pos.fi, pos.se});
for(int i = 0; i < dir; i++){
pii nn = nxt[pos.fi][pos.se][i];
if(cost[r][nn.fi][nn.se] == - 1){
cost[r][nn.fi][nn.se] = cost[r][pos.fi][pos.se] + 1;
q1.push({r, nn.fi, nn.se});
}
}
}
for(int v = 0; v < 300 * N; v++){
while(!q3[v].empty()){
tiiii curr = q3[v].front();
q3[v].pop();
int lo = get<0>(curr), hi = get<1>(curr);
pii pos = {get<2>(curr), get<3>(curr)};
if(dp[lo][hi][pos.fi][pos.se] < v) continue;
for(int i = hi + 1; i < n; i++)
if(dp[lo][i][pos.fi][pos.se] > dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
dp[lo][i][pos.fi][pos.se] = dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
q3[dp[lo][i][pos.fi][pos.se]].push({lo, i, pos.fi, pos.se});
}
for(int i = lo - 1; i >= 0; i--)
if(dp[i][hi][pos.fi][pos.se] > dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
dp[i][hi][pos.fi][pos.se] = dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
q3[dp[i][hi][pos.fi][pos.se]].push({i, hi, pos.fi, pos.se});
}
for(int i = 0; i < dir; i++){
pii nn = nxt[pos.fi][pos.se][i];
if(dp[lo][hi][nn.fi][nn.se] > dp[lo][hi][pos.fi][pos.se] + 1){
dp[lo][hi][nn.fi][nn.se] = dp[lo][hi][pos.fi][pos.se] + 1;
q3[dp[lo][hi][nn.fi][nn.se]].push({lo, hi, nn.fi, nn.se});
}
}
}
}
int ans = inf;
for(int i = 1; i < h - 1; i++)
for(int j = 1; j < w - 1; j++)
ans = min(ans, dp[0][n - 1][i][j]);
if(ans == inf) cout << - 1 << endl;
else cout << ans << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
98 ms |
102392 KB |
Output is correct |
| 2 |
Correct |
98 ms |
102520 KB |
Output is correct |
| 3 |
Correct |
97 ms |
102392 KB |
Output is correct |
| 4 |
Correct |
101 ms |
102520 KB |
Output is correct |
| 5 |
Correct |
102 ms |
102560 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
98 ms |
102392 KB |
Output is correct |
| 2 |
Correct |
98 ms |
102520 KB |
Output is correct |
| 3 |
Correct |
97 ms |
102392 KB |
Output is correct |
| 4 |
Correct |
101 ms |
102520 KB |
Output is correct |
| 5 |
Correct |
102 ms |
102560 KB |
Output is correct |
| 6 |
Correct |
103 ms |
102404 KB |
Output is correct |
| 7 |
Correct |
102 ms |
102404 KB |
Output is correct |
| 8 |
Correct |
101 ms |
102396 KB |
Output is correct |
| 9 |
Correct |
116 ms |
102380 KB |
Output is correct |
| 10 |
Correct |
99 ms |
102520 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
98 ms |
102392 KB |
Output is correct |
| 2 |
Correct |
98 ms |
102520 KB |
Output is correct |
| 3 |
Correct |
97 ms |
102392 KB |
Output is correct |
| 4 |
Correct |
101 ms |
102520 KB |
Output is correct |
| 5 |
Correct |
102 ms |
102560 KB |
Output is correct |
| 6 |
Correct |
103 ms |
102404 KB |
Output is correct |
| 7 |
Correct |
102 ms |
102404 KB |
Output is correct |
| 8 |
Correct |
101 ms |
102396 KB |
Output is correct |
| 9 |
Correct |
116 ms |
102380 KB |
Output is correct |
| 10 |
Correct |
99 ms |
102520 KB |
Output is correct |
| 11 |
Correct |
342 ms |
159512 KB |
Output is correct |
| 12 |
Correct |
114 ms |
106608 KB |
Output is correct |
| 13 |
Correct |
142 ms |
139072 KB |
Output is correct |
| 14 |
Runtime error |
380 ms |
163840 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
98 ms |
102392 KB |
Output is correct |
| 2 |
Correct |
98 ms |
102520 KB |
Output is correct |
| 3 |
Correct |
97 ms |
102392 KB |
Output is correct |
| 4 |
Correct |
101 ms |
102520 KB |
Output is correct |
| 5 |
Correct |
102 ms |
102560 KB |
Output is correct |
| 6 |
Correct |
103 ms |
102404 KB |
Output is correct |
| 7 |
Correct |
102 ms |
102404 KB |
Output is correct |
| 8 |
Correct |
101 ms |
102396 KB |
Output is correct |
| 9 |
Correct |
116 ms |
102380 KB |
Output is correct |
| 10 |
Correct |
99 ms |
102520 KB |
Output is correct |
| 11 |
Correct |
342 ms |
159512 KB |
Output is correct |
| 12 |
Correct |
114 ms |
106608 KB |
Output is correct |
| 13 |
Correct |
142 ms |
139072 KB |
Output is correct |
| 14 |
Runtime error |
380 ms |
163840 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
