Submission #258551

#TimeUsernameProblemLanguageResultExecution timeMemory
258551pure_memRobots (APIO13_robots)C++14
0 / 100
93 ms163844 KiB
#include <bits/stdc++.h> #define ll long long #define X first #define Y second #define MP make_pair using namespace std; const int inf = 250000, N = 501; int n, len, w, h, a[N][N], dp[10][10][N][N]; pair<int, int> end_pos[5][N][N]; queue< pair<int, int> > q[inf]; queue< pair< int, pair< int, int > > > temp; int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(dp, 0x3f, sizeof(dp)); cin >> n >> w >> h; for(int i = 1;i <= h;i++){ for(int j = 1;j <= w;j++){ char x; cin >> x; if(x >= '0' && x <= '9'){ a[i][j] = x - '0'; dp[x - '0'][x - '0'][i][j] = 0; // q.push(MP(MP(i, j), MP(a[i][j], a[i][j]))); } else if(x == 'x'){ a[i][j] = 13; } else if(x == 'A'){ a[i][j] = 11; } else if(x == 'C'){ a[i][j] = 12; } //cerr << a[i][j] << " "; } //cerr << "\n"; } if(n == 1) return cout << 0, 0; for(int x = 1;x <= h;x++){ for(int y = 1;y <= w;y++){ if(a[x][y] == 13 || (x != 1 && x != h && y != 1 && y != w && a[x + 1][y] != 13 && a[x - 1][y] != 13 && a[x][y + 1] != 13 && a[x][y - 1] != 13)) continue; for(int bdr = 1;bdr <= 4;bdr++){ pair<int, int> pos = MP(x, y); int dr = bdr; if(a[pos.X][pos.Y] == 12) dr = (dr + 2) % 4 + 1; else if(a[pos.X][pos.Y] == 11) dr = dr % 4 + 1; while(true){ if(dr == 1){ if(pos.X - 1 >= 1 && pos.X - 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X - 1][pos.Y] != 13) pos.X -= 1; else break; } else if(dr == 2){ if(pos.X >= 1 && pos.X <= h && pos.Y - 1 >= 1 && pos.Y - 1 <= w && a[pos.X][pos.Y - 1] != 13) pos.Y -= 1; else break; } else if(dr == 3){ if(pos.X + 1 >= 1 && pos.X + 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X + 1][pos.Y] != 13) pos.X += 1; else break; } else{ if(pos.X >= 1 && pos.X <= h && pos.Y + 1 >= 1 && pos.Y + 1 <= w && a[pos.X][pos.Y + 1] != 13) pos.Y += 1; else break; } if(end_pos[dr][pos.X][pos.Y] != MP(0, 0)){ pos = end_pos[dr][pos.X][pos.Y]; break; } else{ temp.push(MP(dr, pos)); } if(a[pos.X][pos.Y] == 12) dr = (dr + 2) % 4 + 1; else if(a[pos.X][pos.Y] == 11) dr = dr % 4 + 1; } end_pos[bdr][x][y] = pos; while(!temp.empty()){ end_pos[temp.front().X][temp.front().Y.X][temp.front().Y.Y] = pos; temp.pop(); } } } } int ans = inf; for(len = 1;len < n;len++){ for(int A = 1;A + len - 1 <= n;A++){ int B = A + len - 1; for(int x = 1;x <= h;x++){ for(int y = 1;y <= w;y++){ if(a[x][y] != 13 && dp[A][B][x][y] < inf) q[dp[A][B][x][y]].push(MP(x, y)); } } for(int it = 0;it < inf;it++){ while(!q[it].empty()){ pair<int, int> pos = q[it].front(); q[it].pop(); for(int dr = 1;dr <= 4;dr++){ if(dp[A][B][end_pos[dr][pos.X][pos.Y].X][end_pos[dr][pos.X][pos.Y].Y] > dp[A][B][pos.X][pos.Y] + 1){ dp[A][B][end_pos[dr][pos.X][pos.Y].X][end_pos[dr][pos.X][pos.Y].Y] = dp[A][B][pos.X][pos.Y] + 1; q[it + 1].push(end_pos[dr][pos.X][pos.Y]); } } } } } for(int A = 1;A + len <= n;A++){ for(int C = A;C < A + len;C++){ for(int x = 1;x <= h;x++){ for(int y = 1;y <= w;y++){ if(a[x][y] != 13){ dp[A][A + len][x][y] = min(dp[A][A + len][x][y], dp[A][C][x][y] + dp[C + 1][A + len][x][y]); if(A == 1 && A + len == n) ans = min(ans, dp[A][A + len][x][y]); } } } } } } if(ans >= inf) ans = -1; cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...