#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 = 355, dir = 4, R = 9, inf = 10e8, sum = R * (R + 1) / 2;
pii nxt[N][N][dir];
int cost[R][N][N], dp[sum][N][N], dict[R][R];
//bool vis[sum][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
struct item{
int val;
si lo, hi, r, c;
bool operator < (const item &o) const{
return val > o.val;
}
// item(){}
// item(int val, si lo, si hi, si r, si c) : val(val), lo(lo), hi(hi), pos.fi(r), pos.se(c){}
};
priority_queue<item> q3;
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 < sum; k++)
dp[k][i][j] = inf;
}
int idx = 0;
for(int i = 0; i < R; i++)
for(int j = i; j < R; j++)
dict[i][j] = idx++;
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();
si r = get<0>(curr);
pii pos = {get<1>(curr), get<2>(curr)};
dp[dict[r][r]][pos.fi][pos.se] = cost[r][pos.fi][pos.se];
//vis[dict[r][r]][pos.fi][pos.se] = true;
q3.push({dp[dict[r][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(!q3.empty()){
int val = q3.top().val;
si lo = q3.top().lo;
si hi = q3.top().hi;
pii pos = {q3.top().r, q3.top().c};
q3.pop();
if(lo == 0 && hi == n - 1){
cout << val << endl;
return 0;
}
if(val > dp[dict[lo][hi]][pos.fi][pos.se]) continue;
for(si i = hi + 1; i < n; i++)
if(dp[dict[lo][i]][pos.fi][pos.se] > dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
dp[dict[lo][i]][pos.fi][pos.se] = dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
q3.push({dp[dict[lo][i]][pos.fi][pos.se], lo, i, pos.fi, pos.se});
}
for(si i = lo - 1; i >= 0; i--)
if(dp[dict[i][hi]][pos.fi][pos.se] > dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
dp[dict[i][hi]][pos.fi][pos.se] = dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
q3.push({dp[dict[i][hi]][pos.fi][pos.se], i, hi, pos.fi, pos.se});
}
for(si i = 0; i < dir; i++){
pii nn = nxt[pos.fi][pos.se][i];
if(dp[dict[lo][hi]][nn.fi][nn.se] > dp[dict[lo][hi]][pos.fi][pos.se] + 1){
dp[dict[lo][hi]][nn.fi][nn.se] = dp[dict[lo][hi]][pos.fi][pos.se] + 1;
q3.push({dp[dict[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[dict[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 |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
768 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
768 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1408 KB |
Output is correct |
| 6 |
Correct |
2 ms |
768 KB |
Output is correct |
| 7 |
Correct |
3 ms |
768 KB |
Output is correct |
| 8 |
Correct |
2 ms |
896 KB |
Output is correct |
| 9 |
Correct |
2 ms |
768 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
768 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1408 KB |
Output is correct |
| 6 |
Correct |
2 ms |
768 KB |
Output is correct |
| 7 |
Correct |
3 ms |
768 KB |
Output is correct |
| 8 |
Correct |
2 ms |
896 KB |
Output is correct |
| 9 |
Correct |
2 ms |
768 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1280 KB |
Output is correct |
| 11 |
Correct |
408 ms |
37716 KB |
Output is correct |
| 12 |
Correct |
32 ms |
22392 KB |
Output is correct |
| 13 |
Correct |
37 ms |
24720 KB |
Output is correct |
| 14 |
Execution timed out |
1570 ms |
74684 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
768 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1408 KB |
Output is correct |
| 6 |
Correct |
2 ms |
768 KB |
Output is correct |
| 7 |
Correct |
3 ms |
768 KB |
Output is correct |
| 8 |
Correct |
2 ms |
896 KB |
Output is correct |
| 9 |
Correct |
2 ms |
768 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1280 KB |
Output is correct |
| 11 |
Correct |
408 ms |
37716 KB |
Output is correct |
| 12 |
Correct |
32 ms |
22392 KB |
Output is correct |
| 13 |
Correct |
37 ms |
24720 KB |
Output is correct |
| 14 |
Execution timed out |
1570 ms |
74684 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
