oj.uz

Submission #46915

# Submission time Handle Problem Language Result Execution time Memory
46915 2018-04-24T17:02:02 Z minkank Robots (APIO13_robots) C++17
0 / 100
 77 ms 83192 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];
queue< pair<int, int> > qu[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 (qu[i].size()) {
			pair<int, int> u = qu[i].front(); qu[i].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[i + 1].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) {
				qu[dis[l][r][i][j]].push({i, j});
			}
		}
	}
	bfs(l, r);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> n >> w >> h;

	memset(dis, INF, sizeof dis);
	
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			cin >> a[i][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; else cout << res;

	cerr << '\n' << clock() * 1000 / CLOCKS_PER_SEC;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 83192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 83192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 83192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 83192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -