Submission #915703

#TimeUsernameProblemLanguageResultExecution timeMemory
915703AlcabelRobots (APIO13_robots)C++17
30 / 100
123 ms133456 KiB
#include <bits/stdc++.h> using namespace std; const int maxc = 500, maxn = 10; const int deltaX[4] = {0, -1, 0, 1}, deltaY[4] = {1, 0, -1, 0}; char t[maxc][maxc]; pair<int, int> dest[maxc][maxc][4]; char vis[maxc][maxc][4]; int w, h; pair<int, int> getDest(int x, int y, int dir) { if (vis[x][y][dir] == 1) { dest[x][y][dir] = {-1, -1}; return {-1, -1}; } if (vis[x][y][dir] == 2) { return dest[x][y][dir]; } vis[x][y][dir] = 1; int newDir = dir; if (t[x][y] == 'A') { newDir = (dir < 3 ? dir + 1 : 0); } else if (t[x][y] == 'C') { newDir = (dir > 0 ? dir - 1 : 3); } int newX = x + deltaX[newDir], newY = y + deltaY[newDir]; if (newX < 0 || newX >= h || newY < 0 || newY >= w || t[newX][newY] == 'x') { dest[x][y][dir] = {x, y}; } else { dest[x][y][dir] = getDest(newX, newY, newDir); } vis[x][y][dir] = 2; return dest[x][y][dir]; } const int inf = 1e9; int dist[maxc][maxc]; int dp[maxn][maxn][maxc][maxc]; void bfs(int sx, int sy) { static queue<pair<int, int>> q; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { dist[i][j] = -1; } } dist[sx][sy] = 0; q.emplace(sx, sy); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int dir = 0; dir < 4; ++dir) { auto [newX, newY] = dest[x][y][dir]; if (newX != -1 && dist[newX][newY] == -1) { dist[newX][newY] = dist[x][y] + 1; q.emplace(newX, newY); } } } int num = t[sx][sy] - '1'; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (dist[i][j] != -1) { dp[num][num][i][j] = dist[i][j]; } } } } const int maxd = maxn * maxc * maxc + 10; vector<pair<int ,int>> byDist[maxd]; int distT[maxd], tt; void solve() { int n; cin >> n >> w >> h; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { cin >> t[i][j]; } } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { // cerr << "i: " << i << ", j: " << j << '\n'; for (int dir = 0; dir < 4; ++dir) { if (t[i][j] == 'x') { dest[i][j][dir] = {-1, -1}; vis[i][j][dir] = 2; } else { dest[i][j][dir] = getDest(i, j, dir); } // cerr << "dir: " << dir << ", dest: " << dest[i][j][dir].first << ' ' << dest[i][j][dir].second << '\n'; } } } for (int l = 0; l < n; ++l) { for (int r = 0; r < n; ++r) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { dp[l][r][i][j] = inf; } } } } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (t[i][j] >= '1' && t[i][j] <= '9') { bfs(i, j); } } } tt = 0; for (int len = 2; len <= n; ++len) { for (int l = 0; l + len <= n; ++l) { int r = l + len - 1; // cerr << "l: " << l << ", r: " << r << '\n'; int needcnt = 0, start = inf; ++tt; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { for (int m = l; m < r; ++m) { dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][m][i][j] + dp[m + 1][r][i][j]); } dist[i][j] = dp[l][r][i][j]; if (dist[i][j] != inf) { ++needcnt; if (distT[dist[i][j]] < tt) { distT[dist[i][j]] = tt; byDist[dist[i][j]].clear(); } byDist[dist[i][j]].emplace_back(i, j); start = min(start, dist[i][j]); } // cerr << "i: " << i << ", j: " << j << ", dist: " << dist[i][j] << '\n'; } } while (needcnt > 0) { while (start < maxd && distT[start] < tt) { ++start; } assert(start < maxd); while (!byDist[start].empty()) { auto [i, j] = byDist[start].back(); byDist[start].pop_back(); dp[l][r][i][j] = dist[i][j]; --needcnt; for (int dir = 0; dir < 4; ++dir) { auto [newI, newJ] = dest[i][j][dir]; if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) { int newd = dist[i][j] + 1; dist[newI][newJ] = newd; if (distT[newd] < tt) { distT[newd] = tt; byDist[newd].clear(); } byDist[newd].emplace_back(newI, newJ); } } } ++start; } } } int ans = inf; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ans = min(ans, dp[0][n - 1][i][j]); } } if (ans == inf) { ans = -1; } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int T = 1; cin >> T; while (T--) { solve(); cerr << "-----------\n"; cout << "-----------\n"; } #else int T = 1; // cin >> T; while (T--) { solve(); } #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...