| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1278561 | wedonttalkanymore | 로봇 (APIO13_robots) | C++17 | 0 ms | 0 KiB |
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
/*
Wake up, I'm wake up
Thu sang roi, em thay khong?
*/
using namespace std;
using ll = long long;
// #define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll N = 5e2 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 19;
int n, w, h;
char a[N][N];
int dx[] = {-1, 0, 1, 0}; // tren, phai, duoi, trai
int dy[] = {0, 1, 0, -1};
pii pre[N][N][4];
int dp[N][N][10][10];
pii dfs(int x, int y, int k) {
// cout << x << ' ' << y << ' ' << k << '\n';
// cout << pre[x][y][k].se << '\n';
if (pre[x][y][k].se == -1) {
int nx = 0, ny = 0, nk = k;
pre[x][y][k].se = 0;
if (a[x][y] == 'A') {
nk = (k + 3) % 4;
}
else if (a[x][y] == 'C') {
nk = (k + 1) % 4;
}
// if (x == 2 && y == 2 && k == 2) cout << "at: " << k << ' ' << nk << '\n';
nx = x + dx[nk];
ny = y + dy[nk];
// cout << "now: " << nx << ' ' << ny << ' ' << nk << '\n';
if (nx < 1 || ny < 1 || nx > h || ny > w || a[nx][ny] == 'x') {
pre[x][y][k] = make_pair(x, y);
}
else pre[x][y][k] = dfs(nx, ny, nk);
}
return pre[x][y][k];
}
void precompute() {
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int k = 0; k < 4; k++) {
pre[i][j][k] = make_pair(-1, -1);
}
}
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int k = 0; k < 4; k++) {
dfs(i, j, k);
}
}
}
// dfs(1, 1, 2);
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int k = 0; k < 4; k++) {
// cout << i << ' ' << j << ' ' << k << '\n';
// cout << "now: " << pre[i][j][k].fi << ' ' << pre[i][j][k].se << '\n';
}
}
}
}
struct item {
int x, y, L, R, val;
bool operator <(const item &other) const {
return val > other.val;
}
};
void dijkstra(int len) {
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int R = len; R <= n; R++) {
int L = R - len + 1;
dp[i][j][L][R] = inf;
}
}
}
priority_queue <item> q;
if (len == 1) {
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int R = 1; R <= n; R++) {
if (a[i][j] - '0' == R) {
dp[i][j][R][R] = 0;
// if (len == 1) cout << i << ' ' << j << ' ' << R << '\n';
q.push({i, j, R, R, 0});
}
}
}
}
}
else {
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int R = len; R <= n; R++) {
int L = R - len + 1;
int val = inf;
for (int k = L; k < R; k++) {
val = min(val, dp[i][j][L][k] + dp[i][j][k + 1][R]);
}
if (val < inf) {
dp[i][j][L][R] = val;
q.push({i, j, L, R, val});
}
}
}
}
}
while(q.size()) {
auto [x, y, L, R, val] = q.top();
q.pop();
if (dp[x][y][L][R] < val) continue;
for (int i = 0; i < 4; i++) {
int nx = pre[x][y][i].fi, ny = pre[x][y][i].se;
if (dp[nx][ny][L][R] > dp[x][y][L][R] + 1) {
dp[nx][ny][L][R] = dp[x][y][L][R] + 1;
q.push({nx, ny, L, R, dp[nx][ny][L][R]});
}
}
}
}
void solve() {
for (int len = 1; len <= n; len++) {
dijkstra(len);
}
int ans = inf;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
// cout << i << ' ' << j << ' ' << dp[i][j][1][n] << '\n';
ans = min(ans, dp[i][j][1][n]);
}
}
cout << (ans >= inf ? -1 : ans);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
cin >> n >> w >> h;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> a[i][j];
}
}
precompute();
solve();
return 0;
}