oj.uz

Submission #46921

# Submission time Handle Problem Language Result Execution time Memory
46921 2018-04-24T17:56:13 Z minkank Robots (APIO13_robots) C++17
100 / 100
 603 ms 105540 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) {
	queue< pair<int, int> > qu;

	for (int i = 0; i <= w * h; ++i) {
		while (vec[i].size()) qu.push(vec[i].back()), vec[i].pop_back();

		int sz = qu.size();

		while (sz--) {
			pair<int, int> u = qu.front(); qu.pop();
			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, qu.push(v);
				}
			}
		}
	}
}
 
void go(int l, int r) {
	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() {
	cin >> n >> w >> h; getchar();
 
	for (int l = 1; l <= n; ++l) {
		for (int r = l; r <= n; ++r) {
			for (int i = 1; i <= h; ++i) {
				for (int j = 1; j <= w; ++j) {
					dis[l][r][i][j] = INF;
				}
			}
		}
	}
	
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			a[i][j] = getchar();
			if (a[i][j] >= '1' && a[i][j] <= '9') {
				int x = a[i][j] - '0';
				dis[x][x][i][j] = 0;
			}
		}		
		getchar();
	}
 
	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; else cout << res;
 
	// cerr << '\n' << clock() * 1000 / CLOCKS_PER_SEC;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38264 KB Output is correct
2 Correct 28 ms 38372 KB Output is correct
3 Correct 27 ms 38448 KB Output is correct
4 Correct 28 ms 38524 KB Output is correct
5 Correct 27 ms 38524 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38264 KB Output is correct
2 Correct 28 ms 38372 KB Output is correct
3 Correct 27 ms 38448 KB Output is correct
4 Correct 28 ms 38524 KB Output is correct
5 Correct 27 ms 38524 KB Output is correct
6 Correct 27 ms 38524 KB Output is correct
7 Correct 27 ms 38524 KB Output is correct
8 Correct 27 ms 38524 KB Output is correct
9 Correct 27 ms 38524 KB Output is correct
10 Correct 28 ms 38632 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38264 KB Output is correct
2 Correct 28 ms 38372 KB Output is correct
3 Correct 27 ms 38448 KB Output is correct
4 Correct 28 ms 38524 KB Output is correct
5 Correct 27 ms 38524 KB Output is correct
6 Correct 27 ms 38524 KB Output is correct
7 Correct 27 ms 38524 KB Output is correct
8 Correct 27 ms 38524 KB Output is correct
9 Correct 27 ms 38524 KB Output is correct
10 Correct 28 ms 38632 KB Output is correct
11 Correct 140 ms 69828 KB Output is correct
12 Correct 44 ms 69828 KB Output is correct
13 Correct 85 ms 69828 KB Output is correct
14 Correct 242 ms 72264 KB Output is correct
15 Correct 113 ms 72264 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38264 KB Output is correct
2 Correct 28 ms 38372 KB Output is correct
3 Correct 27 ms 38448 KB Output is correct
4 Correct 28 ms 38524 KB Output is correct
5 Correct 27 ms 38524 KB Output is correct
6 Correct 27 ms 38524 KB Output is correct
7 Correct 27 ms 38524 KB Output is correct
8 Correct 27 ms 38524 KB Output is correct
9 Correct 27 ms 38524 KB Output is correct
10 Correct 28 ms 38632 KB Output is correct
11 Correct 140 ms 69828 KB Output is correct
12 Correct 44 ms 69828 KB Output is correct
13 Correct 85 ms 69828 KB Output is correct
14 Correct 242 ms 72264 KB Output is correct
15 Correct 113 ms 72264 KB Output is correct
16 Correct 211 ms 85876 KB Output is correct
17 Correct 603 ms 105540 KB Output is correct
18 Correct 235 ms 105540 KB Output is correct
19 Correct 237 ms 105540 KB Output is correct
20 Correct 498 ms 105540 KB Output is correct