/// In The Name Of God
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define f first
#define s second
#define pb emplace_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = (int)500 + 1;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n, m, h;
char a[N][N];
int dp[55][N * N];
int id[10][10];
int cid[N][N];
pair <int, int> res[N][N][4];
bool add[N][N][4];
bool was[N][N][4];
struct node {
int l, r, x, y;
inline node() {}
inline node(int l, int r, int x, int y) : l(l), r(r), x(x), y(y) {}
};
vector <node> q[N * N];
inline bool check(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m && a[x][y] != 'x';
}
inline pair <int, int> go(int x, int y, int t) {
if (a[x][y] == 'C') t = (t + 1) % 4;
else if (a[x][y] == 'A') t = (t + 3) % 4;
if (was[x][y][t]) return res[x][y][t];
was[x][y][t] = 1;
if (check(x + dx[t], y + dy[t])) return res[x][y][t] = go(x + dx[t], y + dy[t], t);
return res[x][y][t] = {x, y};
}
int main() {
#ifdef IOI2018
freopen ("in.txt", "r", stdin);
#endif
scanf ("%d%d%d", &h, &m, &n);
int tmr = 0;
for (int i = 0; i <= h; ++i) {
for (int j = i; j <= h; ++j) {
id[i][j] = tmr++;
}
}
/*for (int c = 0; c < tmr; c++)
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[c][i][j] = inf;
for (int cc = 0; cc < 4; cc++) res[i][j][cc].f = -1;
}
}*/
memset(dp, 0x3f, sizeof(dp));
memset(res, -1, sizeof(res));
for (int i = 0; i < n; ++i) {
scanf ("%s", a[i]);
for (int j = 0; j < m; ++j) {
cid[i][j] = i * n + j;
if (isdigit(a[i][j])) {
int d = a[i][j] - '1';
dp[id[d][d]][cid[i][j]] = 0;
q[0].pb(node(d, d, i, j));
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (check(i, j)) {
for (int t = 0; t < 4; t++) {
go(i, j, t);
add[i][j][t] = mp(i, j) != res[i][j][t];
}
}
}
}
int to = n * m;
for (int cur = 0; cur <= to; ++cur) {
while (sz(q[cur])) {
node v = q[cur].back();
q[cur].pp();
if (v.l == 0 && v.r == h - 1) cout << cur, ioi
for (int t = 0; t < 4; ++t) {
pair <int, int> &to = res[v.x][v.y][t];
if (to.f == -1) continue;
//if (mp(v.x, v.y) == to) assert(0);
int &up1 = dp[id[v.l][v.r]][cid[to.f][to.s]];
if (up1 > cur + add[v.x][v.y][t]) {
up1 = cur + add[v.x][v.y][t];
q[up1].pb(node(v.l, v.r, to.f, to.s));
}
for (int i = v.r + 1; i < h; ++i) {
if (dp[id[v.r + 1][i]][cid[to.f][to.s]] >= inf) continue;
int cost = cur + dp[id[v.r + 1][i]][cid[to.f][to.s]] + add[v.x][v.y][t];
int &up2 = dp[id[v.l][i]][cid[to.f][to.s]];
if (up2 > cost) {
up2 = cost;
q[up2].pb(node(v.l, i, to.f, to.s));
}
}
for (int i = 0; i < v.l; ++i) {
if (dp[id[i][v.l - 1]][cid[to.f][to.s]] >= inf) continue;
int cost = cur + dp[id[i][v.l - 1]][cid[to.f][to.s]] + add[v.x][v.y][t];
int &up3 = dp[id[i][v.r]][cid[to.f][to.s]];
if (up3 > cost) {
up3 = cost;
q[up3].pb(node(i, v.r, to.f, to.s));
}
}
}
}
//if (sz(q[cur])) q[cur].clear();
}
cout << -1;
ioi
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", &h, &m, &n);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%s", a[i]);
~~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
68216 KB |
Output is correct |
| 2 |
Correct |
53 ms |
68216 KB |
Output is correct |
| 3 |
Correct |
49 ms |
68252 KB |
Output is correct |
| 4 |
Correct |
51 ms |
68448 KB |
Output is correct |
| 5 |
Correct |
49 ms |
68448 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
68216 KB |
Output is correct |
| 2 |
Correct |
53 ms |
68216 KB |
Output is correct |
| 3 |
Correct |
49 ms |
68252 KB |
Output is correct |
| 4 |
Correct |
51 ms |
68448 KB |
Output is correct |
| 5 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 6 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 7 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 8 |
Correct |
50 ms |
68448 KB |
Output is correct |
| 9 |
Incorrect |
49 ms |
68448 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
68216 KB |
Output is correct |
| 2 |
Correct |
53 ms |
68216 KB |
Output is correct |
| 3 |
Correct |
49 ms |
68252 KB |
Output is correct |
| 4 |
Correct |
51 ms |
68448 KB |
Output is correct |
| 5 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 6 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 7 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 8 |
Correct |
50 ms |
68448 KB |
Output is correct |
| 9 |
Incorrect |
49 ms |
68448 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
68216 KB |
Output is correct |
| 2 |
Correct |
53 ms |
68216 KB |
Output is correct |
| 3 |
Correct |
49 ms |
68252 KB |
Output is correct |
| 4 |
Correct |
51 ms |
68448 KB |
Output is correct |
| 5 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 6 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 7 |
Correct |
49 ms |
68448 KB |
Output is correct |
| 8 |
Correct |
50 ms |
68448 KB |
Output is correct |
| 9 |
Incorrect |
49 ms |
68448 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
