Submission #261608

#TimeUsernameProblemLanguageResultExecution timeMemory
261608DS007Robots (APIO13_robots)C++14
100 / 100
875 ms109688 KiB
#include <bits/stdc++.h> using namespace std; const int N = 9, W = 500; int dp[N][N][W][W], pt[W][W], nxt[W][W][5]; vector<int> adj[W * W]; bool explored[W][W][5]; string a[W]; int n, w, h; int dy[] = {0, 1, 0, -1, 0}; int dx[] = {0, 0, 1, 0, -1}; bool check(int i, int j) { if (i < 0 || j < 0 || i >= h || j >= w || a[i][j] == 'x') return false; return true; } int dfs(int i, int j, int dir) { if (explored[i][j][dir]) return nxt[i][j][dir]; explored[i][j][dir] = true; nxt[i][j][dir] = pt[i][j]; if (a[i][j] != 'A' && a[i][j] != 'C' && a[i][j] != 'x') { if (check(i + dx[dir], j + dy[dir])) return nxt[i][j][dir] = dfs(i + dx[dir], j + dy[dir], dir); else return nxt[i][j][dir] = pt[i][j]; } if (a[i][j] == 'C') { int nd = dir + 1; if (nd == 5) nd = 1; if (check(i + dx[nd], j + dy[nd])) return nxt[i][j][dir] = dfs(i + dx[nd], j + dy[nd], nd); else return nxt[i][j][dir] = pt[i][j]; } if (a[i][j] == 'A') { int nd = dir - 1; if (nd == 0) nd = 4; if (check(i + dx[nd], j + dy[nd])) return nxt[i][j][dir] = dfs(i + dx[nd], j + dy[nd], nd); else return nxt[i][j][dir] = pt[i][j]; } return -1; } void dijkstra(int i, int j) { vector<int> dist[w * h]; bool explored[w * h] = {}; for (int k = 0; k < h; k++) { for (int l = 0; l < w; l++) if (a[k][l] != 'x' && dp[i][j][k][l] < w * h) dist[dp[i][j][k][l]].push_back(pt[k][l]); } for (int i_ = 0; i_ < w * h; i_++) { for (int j_ : dist[i_]) { if (explored[j_]) continue; explored[j_] = true; for (int k : adj[j_]) { if (dp[i][j][k / w][k % w] > i_ + 1) dp[i][j][k / w][k % w] = i_ + 1, dist[i_ + 1].push_back(k); } } } } int solveTestCase() { cin >> n >> w >> h; for (int i = 0; i < h; i++) cin >> a[i]; for (int i = 0; i < h; i++){ for (int j = 0; j < w; j++) pt[i][j] = w * i + j; } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (!explored[i][j][1]) dfs(i, j, 1); if (!explored[i][j][2]) dfs(i, j, 2); if (!explored[i][j][3]) dfs(i, j, 3); if (!explored[i][j][4]) dfs(i, j, 4); adj[pt[i][j]].push_back(nxt[i][j][1]); adj[pt[i][j]].push_back(nxt[i][j][2]); adj[pt[i][j]].push_back(nxt[i][j][3]); adj[pt[i][j]].push_back(nxt[i][j][4]); } } //cerr << check(0 + dx[3], 0 + dy[3]) << "\n"; //cerr << nxt[0][0][1] << " " << nxt[0][0][2] << " " << nxt[0][0][3] << " " << nxt[0][0][4] << "\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < h; k++) { for (int l = 0; l < w; l++) dp[i][j][k][l] = 1e9; } } } for (int i = 0; i < n; i++) { for (int k = 0; k < h; k++) { for (int l = 0; l < w; l++) { if (a[k][l] - '0' == i + 1) dp[i][i][k][l] = 0; } } dijkstra(i, i); } //for (int k = 0; k < h; k++) { // for (int l = 0; l < w; l++) // cerr << dp[0][0][k][l] << " "; // cerr << "\n"; //} for (int dif = 1; dif < n; dif++) { for (int i = 0; i < n; i++) { int j = i + dif; if (j >= n) continue; for (int x = i; x < j; x++) { for (int k = 0; k < h; k++) { for (int l = 0; l < w; l++) dp[i][j][k][l] = min(dp[i][j][k][l], dp[i][x][k][l] + dp[x + 1][j][k][l]); } } dijkstra(i, j); } } int ans = 1e9; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) ans = min(ans, dp[0][n - 1][i][j]); } cout << (ans == 1e9 ? -1 : ans); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while (t--) solveTestCase(); }

Compilation message (stderr)

robots.cpp: In function 'int solveTestCase()':
robots.cpp:162:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...