oj.uz

Submission #1003078

# Submission time Handle Problem Language Result Execution time Memory
1003078 2024-06-20T05:08:37 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 1293 ms 107348 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) x.begin(), x.end()
#define pb push_back
#define x first
#define y second
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

typedef long long ll;

const int maxn = 507;
const int K = 1e5;
const int mod = 1e9 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int s, n, m;
char a[maxn][maxn];
vector <pair <int, int>> act;
pair <int, int> up[maxn][maxn];
pair <int, int> down[maxn][maxn];
pair <int, int> L[maxn][maxn];
pair <int, int> R[maxn][maxn];
vector <pair <int, int>> g[maxn][maxn];
bool used[maxn][maxn];
bool cycle[maxn][maxn][10];
bool udp[10][10][maxn][maxn];
int dp[10][10][maxn][maxn];

bool correct(pair <int, int> p, int vx, int vy) {
	if (p.x == vx && p.y == vy) return false;
	return true;
}

pair <int, int> build(pair <int, int> v, int k) {
	int vx = v.x, vy = v.y;
	if (a[v.x][v.y] == '.') {
		return v;
	} else if (a[v.x][v.y] == 'A') {
		if (k == 1) {
			if (correct(up[vx][vy], vx, vy)) {
				return build(up[vx][vy], 4);
			}
		} else if (k == 2) {
			if (correct(down[vx][vy], vx, vy)) {
				return build(down[vx][vy], 3);
			} 
		} else if (k == 3) {
			if (correct(R[vx][vy], vx, vy)) {
				return build(R[vx][vy], 1);
			}
		} else {
			if (correct(L[vx][vy], vx, vy)) {
				return build(L[vx][vy], 2);
			}
		}
	} else if (a[v.x][v.y] == 'C') {
		if (k == 1) {
			if (correct(down[vx][vy], vx, vy)) {
				return build(down[vx][vy], 3);
			}
		} else if(k == 2) {
			if (correct(up[vx][vy], vx, vy)) {
				return build(up[vx][vy], 4);
			}
		} else if (k == 3) {
			if (correct(L[vx][vy], vx, vy)) {
				return build(L[vx][vy], 2);
			}
		} else {
			if (correct(R[vx][vy], vx, vy)) {
				return build(R[vx][vy], 1);
			}
		}
	}
	return v;
}

void solve() {
	cin >> s >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] >= '1' && a[i][j] <= '9') {
				act.pb({i, j});
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		L[i][0] = {i, 1};
		for (int j = 1; j <= m; j++) {
			L[i][j] = L[i][j - 1];
			if (a[i][j - 1] == 'x') L[i][j] = {i, j};
			if (a[i][j - 1] == 'A' || a[i][j - 1] == 'C') L[i][j] = {i, j - 1};
		}
		R[i][m + 1] = {i, m};
		for (int j = m; j >= 1; j--) {
			R[i][j] = R[i][j + 1];
			if (a[i][j + 1] == 'x') R[i][j] = {i, j};
			if (a[i][j + 1] == 'A' || a[i][j + 1] == 'C') R[i][j] = {i, j + 1};
		}
	}
	for (int j = 1; j <= m; j++) {
		up[0][j] = {1, j};
		for (int i = 1; i <= n; i++) {
			up[i][j] = up[i - 1][j];
			if (a[i - 1][j] == 'x') up[i][j] = {i, j};
			if (a[i - 1][j] == 'A' || a[i - 1][j] == 'C') up[i][j] = {i - 1, j};
		}
		down[n + 1][j] = {n, j};
		for (int i = n; i >= 1; i--) {
			down[i][j] = down[i + 1][j];
			if (a[i + 1][j] == 'x') down[i][j] = {i, j};
			if (a[i + 1][j] == 'A' || a[i + 1][j] == 'C') down[i][j] = {i + 1, j};
		}
	}
	for (int rx = 1; rx <= n; rx++) {
		for (int ry = 1; ry <= m; ry++) {
			if (a[rx][ry] == 'x') continue;
			if (correct(up[rx][ry], rx, ry)) g[rx][ry].pb(build(up[rx][ry], 4));
			if (correct(down[rx][ry], rx, ry)) g[rx][ry].pb(build(down[rx][ry], 3));
			if (correct(R[rx][ry], rx, ry)) g[rx][ry].pb(build(R[rx][ry], 1));
			if (correct(L[rx][ry], rx, ry)) g[rx][ry].pb(build(L[rx][ry], 2));
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int l = 1; l <= s; l++) {
				for (int r = 1; r <= s; r++) {
					dp[l][r][i][j] = 1e9;
				}
			}
		}
	}
	for (auto [rx, ry] : act) {
		int i = a[rx][ry] - '0';
		dp[i][i][rx][ry] = 0;
	}
	for (int sz = 1; sz <= s; sz++) {
		for (int l = 1, r = sz; r <= s; l++, r++) {
			set <pair <int, pair <int, int>>> st;
			for (int x = 1; x <= n; x++) {
				for (int y = 1; y <= m; y++) {
					for (int mid = l; mid < r; mid++) {
						dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][mid][x][y] + dp[mid + 1][r][x][y]);
					}
					if (dp[l][r][x][y] != 1e9) st.insert({dp[l][r][x][y], {x, y}});
				}
			}
			while (!st.empty()) {
				pair <int, int> v = st.begin() -> y;
				st.erase(st.begin());
				for (auto [tox, toy] : g[v.x][v.y]) {
					if (dp[l][r][tox][toy] > dp[l][r][v.x][v.y] + 1) {
						st.erase({dp[l][r][tox][toy], {tox, toy}});
						dp[l][r][tox][toy] = dp[l][r][v.x][v.y] + 1;
						st.insert({dp[l][r][tox][toy], {tox, toy}});
					}
				}
			}
		}
	}
	int ans = 1e9;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans = min(ans, dp[1][s][i][j]);
		}
	}
	if (ans == 1e9) {
		cout << -1;
		return;
	}
	cout << ans;
}
//1 -> L
//2 -> R
//3 -> up
//4 -> down

/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

const bool cases = 0;

signed main() {
//	speed;
	int test = 1, cnt = 0;
	if (cases) cin >> test;
	while (test--) {
		// cout << "Case " << ++cnt << ": ";
		solve();
	}
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:195:16: warning: unused variable 'cnt' [-Wunused-variable]
  195 |  int test = 1, cnt = 0;
      |                ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct
3 Correct 2 ms 6524 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6656 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct
3 Correct 2 ms 6524 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6656 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 3 ms 6744 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct
3 Correct 2 ms 6524 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6656 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 3 ms 6744 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 123 ms 62804 KB Output is correct
12 Correct 11 ms 13400 KB Output is correct
13 Correct 29 ms 42076 KB Output is correct
14 Correct 365 ms 63756 KB Output is correct
15 Correct 72 ms 61776 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct
3 Correct 2 ms 6524 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6656 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 3 ms 6744 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 123 ms 62804 KB Output is correct
12 Correct 11 ms 13400 KB Output is correct
13 Correct 29 ms 42076 KB Output is correct
14 Correct 365 ms 63756 KB Output is correct
15 Correct 72 ms 61776 KB Output is correct
16 Correct 110 ms 106832 KB Output is correct
17 Correct 1293 ms 107348 KB Output is correct
18 Correct 167 ms 103304 KB Output is correct
19 Correct 93 ms 99328 KB Output is correct
20 Correct 704 ms 104584 KB Output is correct