#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, si> tiiiii;
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
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 = 0; i < h; i++){
for(int j = 0; j < w; j++)
cout << grid[i][j] << " ";
cout << endl;
}*/
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});
}
set<tiiiii> s;
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];
s.insert({cost[r][pos.fi][pos.se], 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});
}
}
}
while(!s.empty()){
tiiiii curr = *s.begin();
s.erase(s.begin());
int lo = get<1>(curr), hi = get<2>(curr);
pii pos = {get<3>(curr), get<4>(curr)};
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]){
s.erase({dp[lo][i][pos.fi][pos.se], lo, i, 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];
s.insert({dp[lo][i][pos.fi][pos.se], 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]){
s.erase({dp[i][hi][pos.fi][pos.se], i, 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];
s.insert({dp[i][hi][pos.fi][pos.se], 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){
s.erase({dp[lo][hi][nn.fi][nn.se], lo, hi, nn.fi, nn.se});
dp[lo][hi][nn.fi][nn.se] = dp[lo][hi][pos.fi][pos.se] + 1;
s.insert({dp[lo][hi][nn.fi][nn.se], 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
512 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
512 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
508 KB |
Output is correct |
| 11 |
Execution timed out |
1554 ms |
75600 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
512 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
508 KB |
Output is correct |
| 11 |
Execution timed out |
1554 ms |
75600 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
