oj.uz

Submission #46894

# Submission time Handle Problem Language Result Execution time Memory
46894 2018-04-24T15:17:37 Z minkank Robots (APIO13_robots) C++17
0 / 100
 7 ms 6464 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 505;
const int M = 10;
const int INF = 1e9;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

struct State {
	int x, y, t, d;
};

int n, h, w;
int d1[M][M][N][N];
int d2[N][N][5];
char a[N][N];
vector<State> vec[N * N];

// A -1
// C +1

void bfs() {
	for (int i = 0; i <= w * h; ++i) {
		while (vec[i].size()) {
			State u = vec[i].back(); vec[i].pop_back();
			if (u.d != d2[u.x][u.y][u.t]) continue;
			if (u.t == 0) {
				for (int j = 0; j < 4; ++j) {
					State v = u;
					v.x += dx[j], v.y += dy[j], v.d++, v.t = j + 1;
					if (v.x < 1 || v.y < 1 || v.x > h || v.y > w || a[v.x][v.y] == 'x') continue;
					if (d2[v.x][v.y][v.t] > v.d) {
						d2[v.x][v.y][v.t] = v.d, vec[v.d].push_back(v);
					}
				}
			}
			else {
				State v = u; v.x += dx[u.t - 1], v.y += dy[u.t - 1];
				if (v.x < 1 || v.y < 1 || v.x > h || v.y > w || a[v.x][v.y] == 'x') {
					v = u, v.t = 0;
					if (d2[v.x][v.y][v.t] > v.d) {
						d2[v.x][v.y][v.t] = v.d, vec[v.d].push_back(v);
					}
				}
				else if (a[v.x][v.y] == 'A') {
					v.t--; if (v.t == -1) v.t = 3;
					if (d2[v.x][v.y][v.t] > v.d) {
						d2[v.x][v.y][v.t] = v.d, vec[v.d].push_back(v);
					}
				}
				else if (a[v.x][v.y] == 'C') {
					v.t++; if (v.t == 4) v.t = 0;
					if (d2[v.x][v.y][v.t] > v.d) {
						d2[v.x][v.y][v.t] = v.d, vec[v.d].push_back(v);
					}
				}
				else {
					if (d2[v.x][v.y][v.t] > v.d) {
						d2[v.x][v.y][v.t] = v.d, vec[v.d].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) {
			d2[i][j][0] = d1[l][r][i][j];
			for (int k = 1; k <= 4; ++k) {
				d2[i][j][k] = INF;
			}
			if (d2[i][j][0] <= w * h) {
				vec[d2[i][j][0]].push_back({i, j, 0, d2[i][j][0]});
			}
		}
	}
	bfs();
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			d1[l][r][i][j] = d2[i][j][0];
		}
	}
}

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];
		}
	}
	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) {
					d1[l][r][i][j] = INF;
				}
			}
		}
	}
	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';
				d1[x][x][i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		go(i, i);
		// cout << "#at " << i << '\n';
		// for (int j = 1; j <= h; ++j) {
		// 	for (int k = 1; k <= w; ++k) {
		// 		cout << d1[i][i][j][k] << ' ';
		// 	}
		// 	cout << '\n';
		// }
	}
	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) {
						d1[l][r][j][k] = min(d1[l][r][j][k], d1[l][m][j][k] + d1[m + 1][r][j][k]);
					}
				}
			}
			go(l, r);
		}
	}
	int res = INF;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			res = min(res, d1[1][n][i][j]);
		}
	}
	cout << res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6392 KB Output is correct
2 Incorrect 6 ms 6464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6392 KB Output is correct
2 Incorrect 6 ms 6464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6392 KB Output is correct
2 Incorrect 6 ms 6464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6392 KB Output is correct
2 Incorrect 6 ms 6464 KB Output isn't correct
3 Halted 0 ms 0 KB -