Submission #122074

#TimeUsernameProblemLanguageResultExecution timeMemory
122074jakob_noglerRobots (APIO13_robots)C++14
30 / 100
1554 ms75600 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef short int si; typedef pair<si, si> pii; typedef tuple<si, si, si> tiii; typedef tuple<si, si, si, si, si> tiiiii; const int N = 505, dir = 4, R = 9, inf = 10e8; pii nxt[N][N][dir]; int cost[R][N][N], dp[R][R][N][N]; char grid[N][N]; int n, w, h; int dr[dir] = {1, 0, - 1, 0}; int dc[dir] = {0, 1, 0, - 1}; //down, right, up, left int main(){ cin >> n >> w >> h; w += 2; h += 2; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){ grid[i][j] = 'x'; for(int k = 0; k < dir; k++) nxt[i][j][k] = {- 1, - 1}; for(int k = 0; k < n; k++) cost[k][i][j] = - 1; for(int k = 0; k < n; k++) for(int l = 0; l < n; l++) dp[k][l][i][j] = inf; } queue<tiii> q0, q1; for(int i = 1; i < h - 1; i++) for(int j = 1; j < w - 1; j++){ cin >> grid[i][j]; if(grid[i][j] >= '1' && grid[i][j] <= '9'){ cost[grid[i][j] - '1'][i][j] = 0; q1.push({grid[i][j] - '1', i, j}); } } /*for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++) cout << grid[i][j] << " "; cout << endl; }*/ for(int i = 1; i < h - 1; i++) for(int j = 1; j < w - 1; j++) for(int k = 0; k < dir; k++) if(grid[i][j] != 'x' && grid[i + dr[k]][j + dc[k]] == 'x'){ q0.push({i, j, k}); nxt[i][j][k] = {i, j}; } while(!q0.empty()){ tiii curr = q0.front(); q0.pop(); int d = get<2>(curr), id, mov; pii pos = {get<0>(curr), get<1>(curr)}; if(grid[pos.fi][pos.se] == 'A') mov = (d + 1) % 4, id = (d + 3) % 4; else if(grid[pos.fi][pos.se] == 'C') mov = (d + 3) % 4, id = (d + 1) % 4; else mov = (d + 2) % 4, id = d; if(grid[pos.fi + dr[mov]][pos.se + dc[mov]] == 'x') continue; nxt[pos.fi + dr[mov]][pos.se + dc[mov]][id] = nxt[pos.fi][pos.se][d]; q0.push({pos.fi + dr[mov], pos.se + dc[mov], id}); } set<tiiiii> s; while(!q1.empty()){ tiii curr = q1.front(); q1.pop(); int r = get<0>(curr); pii pos = {get<1>(curr), get<2>(curr)}; dp[r][r][pos.fi][pos.se] = cost[r][pos.fi][pos.se]; s.insert({cost[r][pos.fi][pos.se], r, r, pos.fi, pos.se}); for(int i = 0; i < dir; i++){ pii nn = nxt[pos.fi][pos.se][i]; if(cost[r][nn.fi][nn.se] == - 1){ cost[r][nn.fi][nn.se] = cost[r][pos.fi][pos.se] + 1; q1.push({r, nn.fi, nn.se}); } } } while(!s.empty()){ tiiiii curr = *s.begin(); s.erase(s.begin()); int lo = get<1>(curr), hi = get<2>(curr); pii pos = {get<3>(curr), get<4>(curr)}; for(int i = hi + 1; i < n; i++) if(dp[lo][i][pos.fi][pos.se] > dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){ s.erase({dp[lo][i][pos.fi][pos.se], lo, i, pos.fi, pos.se}); dp[lo][i][pos.fi][pos.se] = dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]; s.insert({dp[lo][i][pos.fi][pos.se], lo, i, pos.fi, pos.se}); } for(int i = lo - 1; i >= 0; i--) if(dp[i][hi][pos.fi][pos.se] > dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){ s.erase({dp[i][hi][pos.fi][pos.se], i, hi, pos.fi, pos.se}); dp[i][hi][pos.fi][pos.se] = dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]; s.insert({dp[i][hi][pos.fi][pos.se], i, hi, pos.fi, pos.se}); } for(int i = 0; i < dir; i++){ pii nn = nxt[pos.fi][pos.se][i]; if(dp[lo][hi][nn.fi][nn.se] > dp[lo][hi][pos.fi][pos.se] + 1){ s.erase({dp[lo][hi][nn.fi][nn.se], lo, hi, nn.fi, nn.se}); dp[lo][hi][nn.fi][nn.se] = dp[lo][hi][pos.fi][pos.se] + 1; s.insert({dp[lo][hi][nn.fi][nn.se], lo, hi, nn.fi, nn.se}); } } } int ans = inf; for(int i = 1; i < h - 1; i++) for(int j = 1; j < w - 1; j++) ans = min(ans, dp[0][n - 1][i][j]); if(ans == inf) cout << - 1 << endl; else cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...