#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 503;
int m, n, k;
const int X[] = {0, 1, 0, -1};
const int Y[] = {1, 0, -1, 0};
typedef pair < int, int > ii;
ii nxt[N][N][4];
bool vs[N][N][4];
int dp[N][N][10][10];
char a[N][N];
typedef pair < ii, ii > iii;
queue < iii > val[N * N];
bool thoaman(int i, int j)
{
if (i < 1 || j < 1 || i > m || j > n) return false;
if (a[i][j] == 'x') return false;
return true;
}
ii tim_pos(int i, int j, int dir)
{
//cout << i << " " << j << " " << dir << '\n';
if (vs[i][j][dir]) return nxt[i][j][dir];
vs[i][j][dir] = true;
int nxt_i = i + X[dir], nxt_j = j + Y[dir];
if (!thoaman(nxt_i, nxt_j))
nxt[i][j][dir] = {i, j};
if (a[nxt_i][nxt_j] == '.')
nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, dir);
if ('1' <= a[nxt_i][nxt_j] && a[nxt_i][nxt_j] <= '9')
nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, dir);
if (a[nxt_i][nxt_j] == 'A')
nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, (dir + 3) % 4);
if (a[nxt_i][nxt_j] == 'C')
nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, (dir + 1) % 4);
return nxt[i][j][dir];
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("t.inp","r",stdin); freopen("t.out","w",stdout);
cin >> k >> n >> m;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
for (int t = 0; t < 4; t++)
nxt[i][j][t] = {-1, -1};
}
memset(vs, false, sizeof vs);
memset(dp, 0x3f, sizeof dp);
tim_pos(5, 5, 0);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a[i][j] != 'x')
{
for (int t = 0; t < 4; t++)
nxt[i][j][t] = tim_pos(i, j, t);
int cs = 0;
if ('1' <= a[i][j] && a[i][j] <= '9')
dp[i][j][a[i][j] - '1' + 1][a[i][j] - '1' + 1] = 0,
cs = a[i][j] - '1' + 1,
val[0].push({{i, j}, {cs, cs}});
}
int res = 1e9 + 3;
for (int gt = 0; gt <= m * n; gt++)
while (val[gt].size())
{
iii cur = val[gt].front();
int i = cur.fi.fi, j = cur.fi.se;
int lo = cur.se.fi, hi = cur.se.se;
val[gt].pop();
if (dp[i][j][lo][hi] != gt) continue;
if (lo == 1 && hi == k)
{
res = min(res, gt);
cout << res;
return 0;
}
for (int u = lo - 1; u >= 1; u--)
if (dp[i][j][u][lo - 1] < 1e9 && dp[i][j][u][hi] > dp[i][j][u][lo - 1] + dp[i][j][lo][hi])
{
dp[i][j][u][hi] = dp[i][j][u][lo - 1] + dp[i][j][lo][hi];
val[dp[i][j][u][hi]].push({{i, j}, {u, hi}});
if (u == 1 && hi == k) res = min(res, dp[i][j][u][hi]);
}
for (int v = hi + 1; v <= k; v++)
if (dp[i][j][hi + 1][v] < 1e9 && dp[i][j][lo][v] > dp[i][j][lo][hi] + dp[i][j][hi + 1][v])
{
dp[i][j][lo][v] = dp[i][j][hi + 1][v] + dp[i][j][lo][hi];
val[dp[i][j][lo][v]].push({{i, j}, {lo, v}});
if (lo == 1 && v == k) res = min(res, dp[i][j][lo][v]);
}
for (int u = lo - 1; u >= 1; u--)
for (int v = hi + 1; v <= k; v++)
if (dp[i][j][u][lo - 1] < 1e9 && dp[i][j][hi + 1][v] < 1e9)
{
if (dp[i][j][u][v] > dp[i][j][u][lo - 1] + gt + dp[i][j][hi + 1][v])
{
dp[i][j][u][v] = dp[i][j][u][lo - 1] + gt + dp[i][j][hi + 1][v];
val[dp[i][j][u][v]].push({{i, j}, {u, v}});
if (u == 1 && v == k) res = min(res, dp[i][j][u][v]);
}
}
res = min(res, dp[i][j][1][k]);
for (int t = 0; t < 4; t++)
{
int nxt_i = nxt[i][j][t].fi, nxt_j = nxt[i][j][t].se;
if (nxt_i == -1) continue;
if (dp[nxt_i][nxt_j][lo][hi] > gt + 1)
{
dp[nxt_i][nxt_j][lo][hi] = gt + 1;
val[gt + 1].push({{nxt_i, nxt_j}, {lo, hi}});
}
}
}
if (res > 1e9) res = -1;
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
