#include <cstdio>
#include <cstring>
#include <utility>
#include <functional>
#include <queue>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=1;i<=n;++i)
#define x first
#define y second
#define eb emplace_back
using namespace std;
using pp=pair<int,int>;
int n, m, k;
char q[510][510];
pp e[510][510][4];
pp il[10];
using t4=tuple<int,int,int,int>;
int dp[510][510][50];
bool iq[510][510][50];
const int dx[5] = {0, 1, 0, -1}, *dy = dx+1;
pp E(int x, int y, int d) {
pp &ret = e[x][y][d];
if (ret.x) return ret;
int nx=x+dx[d], ny=y+dy[d];
if (1<=nx && nx<=n && 1<=ny && ny<=m && q[nx][ny]!='x') {
switch(q[nx][ny]) {
case 'A': ret = E(nx, ny, (d+3)%4); break;
case 'C': ret = E(nx, ny, (d+1)%4); break;
default: ret = E(nx, ny, d); break;
}
return ret;
} else return ret={x, y};
}
int C[10][10];
priority_queue<pair<int,t4>> Q[10];
int main()
{
scanf("%d%d%d",&k,&m,&n);
rrep(i, n) {
scanf("%s", q[i]+1);
rrep(j, m) if ((q[i][j]&48)==48) il[q[i][j]-48]={i,j};
}
{ static int p = 0; rrep(i, k) rrep(j, i) C[j][i] = ++p; }
memset(dp,0x3f,sizeof(dp));
rrep(i, k) {
Q[1].emplace(0, t4{il[i].x, il[i].y, i, i});
dp[il[i].x][il[i].y][C[i][i]] = 0;
iq[il[i].x][il[i].y][C[i][i]] = 1;
}
rrep(len, k) {
while(Q[len].size()) {
int x,y,l,r,od;
od = -Q[len].top().x;
tie(x,y,l,r) = Q[len].top().y; Q[len].pop();
int p = C[l][r];
if (od != dp[x][y][p]) continue;
rep(d, 4) {
pp t = E(x, y, d);
if (t == pp(x, y)) continue;
if (dp[t.x][t.y][p] > dp[x][y][p]+1) {
dp[t.x][t.y][p] = dp[x][y][p]+1;
if (!iq[t.x][t.y][p]) {
iq[t.x][t.y][p] = 1;
Q[len].emplace(
-dp[t.x][t.y][p],
t4{t.x, t.y, l, r});
}
}
}
auto R = [&](int l, int r, int v) {
int np = C[l][r];
if (dp[x][y][np] > v) {
dp[x][y][np] = v;
if (!iq[x][y][np]) iq[x][y][np]=1,
Q[r-l+1].emplace(-v,
t4{x, y, l, r});
}
};
for(int i=1; i<l; ++i) if ((l-i) <= (r-l+1))
R(i, r,
dp[x][y][C[i][l-1]] + dp[x][y][p]);
for(int i=r+1; i<=k; ++i) if ((i-r) <= (r-l+1))
R(l, i,
dp[x][y][C[r+1][i]] + dp[x][y][p]);
}
}
int inf = 0x3f3f3f3f, ans = inf;
rrep(i, n) rrep(j, m)
ans = min(ans, dp[i][j][C[1][k]]);
if (ans == inf) ans = -1;
printf("%d\n", ans);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
44 | scanf("%d%d%d",&k,&m,&n);
| ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
46 | scanf("%s", q[i]+1);
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
51192 KB |
Output is correct |
2 |
Correct |
32 ms |
51284 KB |
Output is correct |
3 |
Correct |
30 ms |
51200 KB |
Output is correct |
4 |
Correct |
30 ms |
51328 KB |
Output is correct |
5 |
Correct |
30 ms |
51328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
51192 KB |
Output is correct |
2 |
Correct |
32 ms |
51284 KB |
Output is correct |
3 |
Correct |
30 ms |
51200 KB |
Output is correct |
4 |
Correct |
30 ms |
51328 KB |
Output is correct |
5 |
Correct |
30 ms |
51328 KB |
Output is correct |
6 |
Correct |
30 ms |
51192 KB |
Output is correct |
7 |
Correct |
30 ms |
51192 KB |
Output is correct |
8 |
Correct |
31 ms |
51196 KB |
Output is correct |
9 |
Correct |
31 ms |
51192 KB |
Output is correct |
10 |
Correct |
30 ms |
51320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
51192 KB |
Output is correct |
2 |
Correct |
32 ms |
51284 KB |
Output is correct |
3 |
Correct |
30 ms |
51200 KB |
Output is correct |
4 |
Correct |
30 ms |
51328 KB |
Output is correct |
5 |
Correct |
30 ms |
51328 KB |
Output is correct |
6 |
Correct |
30 ms |
51192 KB |
Output is correct |
7 |
Correct |
30 ms |
51192 KB |
Output is correct |
8 |
Correct |
31 ms |
51196 KB |
Output is correct |
9 |
Correct |
31 ms |
51192 KB |
Output is correct |
10 |
Correct |
30 ms |
51320 KB |
Output is correct |
11 |
Incorrect |
296 ms |
70872 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
51192 KB |
Output is correct |
2 |
Correct |
32 ms |
51284 KB |
Output is correct |
3 |
Correct |
30 ms |
51200 KB |
Output is correct |
4 |
Correct |
30 ms |
51328 KB |
Output is correct |
5 |
Correct |
30 ms |
51328 KB |
Output is correct |
6 |
Correct |
30 ms |
51192 KB |
Output is correct |
7 |
Correct |
30 ms |
51192 KB |
Output is correct |
8 |
Correct |
31 ms |
51196 KB |
Output is correct |
9 |
Correct |
31 ms |
51192 KB |
Output is correct |
10 |
Correct |
30 ms |
51320 KB |
Output is correct |
11 |
Incorrect |
296 ms |
70872 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |