#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef U_U
#include "algo/debug.h"
#else
#define deb(x...) 42
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define szof(x) (int)x.size()
//#define int ll
#define love bool
template<class T> void MIN(T& a, const T b) { b < a ? a = b, 1 : 0; }
template<class T> void MAX(T& a, const T b) { a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int inf = 2147483647;
const int INF = 9223372036854775807;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
// Follow the white rabbit.
int n, m, nn;
char e[505][505];
int dist[505][505][10];
vector <pair <int, int> > g[505][505];
vector <pair <int, int> > v(11);
pair <int, int> was[505][505][10];
bool can (int x, int y) {
if (x > n || x < 1 || y > m || y < 1 || e[x][y] == 'x') return 0;
return 1;
}
pair <int, int> get (int x, int y, int k) {
if (was[x][y][k].first) return was[x][y][k];
was[x][y][k] = {-1, -1};
int tmp = k;
if (e[x][y] == 'A') k += 3, k %= 4;
if (e[x][y] == 'C') k ++, k %= 4;
int X = dx[k] + x, Y = dy[k] + y;
if (can(X, Y)) {
return was[x][y][tmp] = get(X, Y, k);
}
return was[x][y][tmp] = {x, y};
}
int dp[10][10][505][505];
void ka () {
cin >> nn >> m >> n;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> e[i][j];
if (e[i][j] >= '1' && e[i][j] <= '9') v[e[i][j] - '0'] = {i, j};
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (!can(i, j)) continue;
for (int k = 0; k < 4; k ++) {
pair <int, int> tmp = get(i, j, k);
if (tmp.first != -1) g[i][j].pb(tmp);
}
}
}
for (int l = 1; l <= nn; l ++) {
for (int r = l; r <= nn; r ++) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
dp[l][r][i][j] = inf;
}
}
}
}
for (int i = 1; i <= nn; i ++) {
dp[i][i][v[i].first][v[i].second] = 0;
}
for (int len = 1; len <= nn; len ++) {
for (int l = 1; l <= nn; l ++) {
int r = l + len - 1;
if (r > nn) break;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
for (int md = l; md < r; md ++) {
MIN(dp[l][r][i][j], dp[l][md][i][j] + dp[md + 1][r][i][j]);
}
}
}
set <pair <int, pair <int, int> > > q;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (dp[l][r][i][j] != inf) q.insert({dp[l][r][i][j], {i, j}});
}
}
while (szof(q)) {
pair <int, pair <int, int> > tmp = *q.begin();
q.erase(tmp);
for (pair <int, int> c : g[tmp.second.first][tmp.second.second]) {
if (dp[l][r][c.first][c.second] > dp[l][r][tmp.second.first][tmp.second.second] + 1) {
q.erase({dp[l][r][c.first][c.second], c});
dp[l][r][c.first][c.second] = dp[l][r][tmp.second.first][tmp.second.second] + 1;
q.insert({dp[l][r][c.first][c.second], c});
}
}
}
}
}
int ans = inf;
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) MIN(ans, dp[1][nn][i][j]);
cout << (ans == inf ? -1 : ans);
}
const bool overflow = 0;
main() {
//freopen("haircut.in" , "r", stdin); freopen("haircut.out", "w", stdout);
cout.setf(ios::fixed);cout.precision(12);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc = 1;
if (overflow) cin >> tc;
for (int cs = 1; cs <= tc; cs ++) {
#ifdef U_U
cout << ":D\n";
#endif
ka();
//if (cs != tc) cout << '\n';
}
}
Compilation message
robots.cpp:24:17: warning: overflow in conversion from 'long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
24 | const int INF = 9223372036854775807;
| ^~~~~~~~~~~~~~~~~~~
robots.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
118 | main() {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
