Submission #1125438

#TimeUsernameProblemLanguageResultExecution timeMemory
1125438ALTAKEXERobots (APIO13_robots)C++17
10 / 100
5 ms6728 KiB
#include <bits/stdc++.h> #define ll long long #define x first #define y second #define inf INT_MAX #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define FAR(i, a, b) for (int i = (a); i >= (b); i--) #define all(x) (x.begin(), x.end()) const int MOD = 1e9 + 7; using namespace std; 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 (!cycle[vx][vy][k]) { cycle[vx][vy][k] = 1; 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]; } int main() { 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.push_back({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].push_back(build(up[rx][ry], 4)); if (correct(down[rx][ry], rx, ry)) g[rx][ry].push_back(build(down[rx][ry], 3)); if (correct(R[rx][ry], rx, ry)) g[rx][ry].push_back(build(R[rx][ry], 1)); if (correct(L[rx][ry], rx, ry)) g[rx][ry].push_back(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) { 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 = 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 0; } cout << ans; } // 1 -> L // 2 -> R // 3 -> up // 4 -> down /* 4 10 5 1......... AA...x4... ..A..x.... 2....x.... ..C.3.A... */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...