// apio-13-p1-robots.yml
#include "bits/stdc++.h"
using namespace std;
// Defines
#define pb push_back
#define mpr make_pair
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
// Basic type definitions
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<long long, long long>;
// PBDS order statistic tree
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T, class comp = less<T>> using os_tree = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V, class comp = less<K>> using treemap = tree<K, V, comp, rb_tree_tag, tree_order_statistics_node_update>;
// HashSet
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash { ll operator()(ll x) const { return x ^ RANDOM; } };
template <typename T, class Hash> using hashset = gp_hash_table<T, null_type, Hash>;
template <typename K, typename V, class Hash> using hashmap = gp_hash_table<K, V, Hash>;
// More utilities
template <typename C> int SZ(C &v) { return v.size(); }
template <typename T, typename U> void maxa(T &a, U b) { a = max(a, b); }
template <typename T, typename U> void mina(T &a, U b) { a = min(a, b); }
const ll INF = 0x3f3f3f3f, LLINF = 0x3f3f3f3f3f3f3f3f;
int mk(int a, int b) {
return (a << 10) | b;
}
int fst(int p) { return p >> 10; }
int snd(int p) { return p & 1023; }
const int MN = 501, DIR[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const int DEF_PII = mk(INF, INF), DEF_INVALID = mk(-1, -1);
int N, W, H;
char grid[MN][MN];
int toPos[MN][MN][4];
bool instk[MN][MN];
stack<int> stk;
int compute(int x, int y, int dir) {
auto &res = toPos[x][y][dir];
if (res != DEF_PII) return res;
if (grid[x][y] == 'x') return res = mk(-1, -1);
stk.push(mk(x, y));
instk[x][y] = true;
int nx = x + DIR[dir][0], ny = y + DIR[dir][1];
if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
if (instk[nx][ny]) res = mk(-1, -1);
else if (grid[nx][ny] == 'x') res = mk(x, y);
else if (grid[nx][ny] == 'A') res = compute(nx, ny, (dir + 3) % 4);
else if (grid[nx][ny] == 'C') res = compute(nx, ny, (dir + 1) % 4);
else res = compute(nx, ny, dir);
}
else res = mk(x, y);
stk.pop();
instk[x][y] = false;
return res;
}
int spos[10];
int dp[10][10][MN][MN];
// BFS
int dis[2][MN][MN];
queue<int> q;
// mode=0->init bfs (a is startnum), mode=1->bfs from level (a..b is level), mode=2->mode=1 but using dis[0]
void bfs(int didx, int mode, int a, int b) {
vector<pii> ins;
if (mode == 0) {
ins.emplace_back(0, spos[a]); }
else if (mode == 1) {
for (auto i = 0; i < H; i++)
for (auto j = 0; j < W; j++)
ins.emplace_back(dp[a][b][i][j], mk(i, j));
}
else {
for (auto i = 0; i < H; i++)
for (auto j = 0; j < W; j++)
ins.emplace_back(dis[0][i][j], mk(i, j));
}
sort(all(ins), greater<pii>());
#define D dis[didx]
#define PUSH_POS auto &ipos = ins.back().second; \
if (D[fst(ipos)][snd(ipos)] == INF) { \
D[fst(ipos)][snd(ipos)] = ins.back().first; \
q.push(ipos); \
} \
ins.pop_back();
while (!ins.empty()) {
PUSH_POS;
while (!q.empty()) {
auto c = q.front(); q.pop();
int cdis = D[fst(c)][snd(c)];
for (auto to : toPos[fst(c)][snd(c)]) {
if (to == DEF_INVALID) continue;
if (D[fst(to)][snd(to)] == INF) {
D[fst(to)][snd(to)] = cdis + 1;
while (!ins.empty() && ins.back().first < cdis + 1) {
PUSH_POS;
}
q.push(to);
}
}
}
}
#undef D
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> (N) >> (W) >> (H);
for (auto i = 0; i < H; i++) {
cin >> (grid[i]);
for (auto j = 0; j < W; j++) {
if ('1' <= grid[i][j] && grid[i][j] <= '9') {
spos[grid[i][j] - '0'] = mk(i, j); }
}
}
// Compute
for (auto i = 0; i < H; i++)
for (auto j = 0; j < W; j++)
for (auto k = 0; k < 4; k++)
toPos[i][j][k] = mk(INF, INF);
for (auto i = 0; i < H; i++)
for (auto j = 0; j < W; j++)
for (auto k = 0; k < 4; k++)
compute(i, j, k);
memset(dp, 0x3f, sizeof dp);
for (int len = 1; len <= N; len++) {
int end = N - len + 1;
for (auto l = 1; l <= end; l++) {
#define EXTEND(P) for (int i = 0; i < H; i++) \
for (int j = 0; j < W; j++) \
mina(dp[l][r][i][j], dis[P][i][j]);
int r = l + len - 1;
if (l == r) {
memset(dis[0], 0x3f, sizeof dis[0]);
bfs(0, 0, l, -1);
EXTEND(0);
}
else {
for (auto k = l; k < r; k++) {
int ctr = 0;
for (auto iv : vector<pii>{{l, k}, {k + 1, r}}) {
memset(dis[ctr], 0x3f, sizeof dis[ctr]);
bfs(ctr, 1, iv.first, iv.second);
ctr++;
}
for (auto i = 0; i < H; i++)
for (auto j = 0; j < W; j++)
dis[0][i][j] += dis[1][i][j];
memset(dis[1], 0x3f, sizeof dis[1]);
bfs(1, 2, -1, -1);
EXTEND(1);
}
}
// for (auto i = 0; i < H; i++) {
// for (auto j = 0; j < W; j++) {
// cout<<"l="<<(l)<<", "; cout<<"r="<<(r)<<", "; cout<<"i="<<(i)<<", "; cout<<"j="<<(j)<<", "; cout<<"dp[l][r][i][j]="<<(dp[l][r][i][j])<<", "; cout << endl; // db l,r,i,j,dp[l][r][i][j]
// }
// }
}
}
int ans = INF;
for (auto i = 0; i < H; i++)
for (auto j = 0; j < W; j++)
mina(ans, dp[1][N][i][j]);
cout << ((ans == INF ? -1 : ans)) << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 2 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 3 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 4 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 5 |
Correct |
48 ms |
100728 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 2 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 3 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 4 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 5 |
Correct |
48 ms |
100728 KB |
Output is correct |
| 6 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 7 |
Correct |
47 ms |
100520 KB |
Output is correct |
| 8 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 9 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 10 |
Correct |
47 ms |
100600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 2 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 3 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 4 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 5 |
Correct |
48 ms |
100728 KB |
Output is correct |
| 6 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 7 |
Correct |
47 ms |
100520 KB |
Output is correct |
| 8 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 9 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 10 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 11 |
Execution timed out |
1595 ms |
105148 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 2 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 3 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 4 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 5 |
Correct |
48 ms |
100728 KB |
Output is correct |
| 6 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 7 |
Correct |
47 ms |
100520 KB |
Output is correct |
| 8 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 9 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 10 |
Correct |
47 ms |
100600 KB |
Output is correct |
| 11 |
Execution timed out |
1595 ms |
105148 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
