Submission #915694

#TimeUsernameProblemLanguageResultExecution timeMemory
915694AlcabelRobots (APIO13_robots)C++17
60 / 100
1569 ms100784 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]; char tmpvis[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]; } } } } 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); } } } priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q; 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'; 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]); } tmpvis[i][j] = false; dist[i][j] = dp[l][r][i][j]; // cerr << "i: " << i << ", j: " << j << ", dist: " << dist[i][j] << '\n'; q.emplace(dist[i][j], i, j); } } while (!q.empty()) { auto [d, i, j] = q.top(); // cerr << "d: " << d << ", i: " << i << ", j: " << j << '\n; q.pop(); if (tmpvis[i][j]) { continue; } dp[l][r][i][j] = dist[i][j]; tmpvis[i][j] = true; for (int dir = 0; dir < 4; ++dir) { auto [newI, newJ] = dest[i][j][dir]; if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) { dist[newI][newJ] = dist[i][j] + 1; q.emplace(dist[newI][newJ], newI, newJ); } } } } } /*cerr << dp[2][2][0][6] << '\n'; cerr << dp[3][3][0][6] << '\n'; cerr << dp[2][3][0][6] << '\n'; cerr << dp[1][1][0][0] << '\n'; cerr << dp[0][0][0][0] << '\n'; cerr << dp[0][1][0][0] << '\n';*/ 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...