| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 46909 |
2018-04-24T16:48:42 Z |
minkank |
Robots (APIO13_robots) |
C++17 |
|
95 ms |
138104 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 505;
const int M = 10;
const int INF = 0x3f3f3f3f;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
struct State {
pair<int, int> p;
int x, y;
State() {}
State (pair<int, int> p, int x, int y) :
p(p), x(x), y(y) {}
};
int n, h, w;
int dis[M][M][N][N];
State nxt[N][N][4][2];
bool visit[N][N][4][2];
char a[N][N];
vector< pair<int, int> > vec[N * N];
// A -1
// C +1
State dfs(int r, int c, int x, int y) {
if (visit[r][c][x][y]) return nxt[r][c][x][y];
visit[r][c][x][y] = 1;
if (y == 0 && (a[r][c] == 'A' || a[r][c] == 'C')) {
int nx = x;
if (a[r][c] == 'A') {
nx--; if (nx == -1) nx = 3;
}
else {
nx++; if (nx == 4) nx = 0;
}
return nxt[r][c][x][y] = dfs(r, c, nx, 1);
}
else {
int nr, nc;
nr = r + dr[x], nc = c + dc[x];
if (nr < 1 || nc < 1 || nr > h || nc > w || a[nr][nc] == 'x') {
return nxt[r][c][x][y] = State({r, c}, x, y);
}
else {
return nxt[r][c][x][y] = dfs(nr, nc, x, 0);
}
}
}
void bfs(int l, int r) {
for (int i = 0; i <= w * h; ++i) {
while (vec[i].size()) {
pair<int, int> u = vec[i].back(); vec[i].pop_back();
if (dis[l][r][u.fi][u.se] != i) continue;
for (int j = 0; j < 4; ++j) {
pair<int, int> v = nxt[u.fi][u.se][j][1].p;
if (dis[l][r][v.fi][v.se] > i + 1) {
dis[l][r][v.fi][v.se] = i + 1, vec[i + 1].push_back(v);
}
}
}
}
}
void go(int l, int r) {
for (int i = 0; i <= w * h; ++i) vec[i].clear();
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
if (dis[l][r][i][j] <= w * h) {
vec[dis[l][r][i][j]].push_back({i, j});
}
}
}
bfs(l, r);
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> w >> h;
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
cin >> a[i][j];
}
}
memset(dis, INF, sizeof dis);
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
if (a[i][j] >= '1' && a[i][j] <= '9') {
int x = a[i][j] - '0';
dis[x][x][i][j] = 0;
}
}
}
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, 1);
// cout << "#nxt " << i << ' ' << j << ' ' << k << ":\n";
// cout << nxt[i][j][k][1].p.fi << ' ' << nxt[i][j][k][1].p.se << '\n';
}
}
}
for (int i = 1; i <= n; ++i) go(i, i);
for (int i = 2; i <= n; ++i) {
for (int l = 1; l + i - 1 <= n; ++l) {
int r = l + i - 1;
for (int m = l; m < r; ++m) {
for (int j = 1; j <= h; ++j) {
for (int k = 1; k <= w; ++k) {
dis[l][r][j][k] = min(dis[l][r][j][k], dis[l][m][j][k] + dis[m + 1][r][j][k]);
}
}
}
go(l, r);
}
}
// for (int l = 1; l <= n; ++l) {
// for (int r = l; r <= n; ++r) {
// cout << "#at " << l << ' ' << r << '\n';
// for (int i = 1; i <= h; ++i) {
// for (int j = 1; j <= w; ++j) {
// cout << dis[l][r][i][j] << ' ';
// }
// cout << '\n';
// }
// }
// }
int res = INF;
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
res = min(res, dis[1][n][i][j]);
}
}
if (res == INF) cout << -1 << '\n'; else cout << res << '\n';
cerr << clock() * 1000 / CLOCKS_PER_SEC;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
138104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
138104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
138104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
138104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
