oj.uz

답안 #1003067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003067 2024-06-20T05:01:37 Z vjudge1 로봇 (APIO13_robots) C++17
30 / 100
 1500 ms 119896 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 int long long
#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;
	set <pair <int, int>> st;
	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;
}

int solve(int l, int r, int x, int y) {
	if (udp[l][r][x][y]) return dp[l][r][x][y];
	udp[l][r][x][y] = 1;
	for (int mid = l; mid < r; mid++) {
		dp[l][r][x][y] = min(dp[l][r][x][y], solve(l, mid, x, y) + solve(mid + 1, r, x, y));
	}
	set <pair <int, pair <int, int>>> st;
	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 (solve(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}});
			}
		}
	}
	return dp[l][r][x][y];
}

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] = 1e18;
				}
			}
		}
	}
	for (auto [rx, ry] : act) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				used[i][j] = 0;
			}
		}
		queue <pair <int, int>> q;
		q.push({rx, ry});
		used[rx][ry] = 1;
		int x = (a[rx][ry] - '0');
		dp[x][x][rx][ry] = 0;
		while (q.size()) {
			pair <int, int> v = q.front();
			q.pop();
			for (auto [tox, toy] : g[v.x][v.y]) {
				if (!used[tox][toy]) {
					used[tox][toy] = 1;
					dp[x][x][tox][toy] = dp[x][x][v.x][v.y] + 1;
					q.push({tox, toy});
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			solve(1, s, i, j);
		}
	}
	int ans = 1e18;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans = min(ans, dp[1][s][i][j]);
		}
	}
	if (ans == 1e18) {
		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:219:16: warning: unused variable 'cnt' [-Wunused-variable]
  219 |  int test = 1, cnt = 0;
      |                ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6488 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6488 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Execution timed out 1554 ms 119896 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6488 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Execution timed out 1554 ms 119896 KB Time limit exceeded
12 Halted 0 ms 0 KB -