Submission #1166812

#TimeUsernameProblemLanguageResultExecution timeMemory
1166812KerimRobots (APIO13_robots)C++20
100 / 100
1345 ms117476 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define ll long long const int N = 505; char a[N][N]; int mp[N][N], n, w, h, ind[10], nd, dpfn[10][10][N*N]; pair <int, int> dp[N][N][4]; vector <vector <int>> v; pair <int, int> f(int i, int j, int x) { if(dp[i][j][x] != pair <int, int> {0, 0}) return dp[i][j][x]; int x1 = (x % 2 ? 0 : (!x ? -1 : 1)), y1 = (!(x % 2) ? 0 : (x == 1 ? 1 : -1)); if(a[i + x1][j + y1] != 'x' and i + x1 <= h and i + x1 > 0 and j + y1 <= w and j + y1 > 0) { int xx = x, i1 = i, j1 = j; i += x1, j += y1; if(a[i][j] == 'C') { x++; if(x == 4) x = 0; } if(a[i][j] == 'A') { x--; if(x == -1) x = 3; } return dp[i1][j1][xx] = f(i, j, x); } return dp[i][j][x] = pair <int, int> {i, j}; } void compute(int a, int b, vector <pair <int, int>>&q2){ queue<pair<int,int> > q; while(!q.empty() or !q2.empty()) { bool ok = 0; if (q2.empty()) ok = 1; else if (!q.empty() && q.front().first < q2.back().first) ok = 1; auto [cost, x] = ok ? q.front() : q2.back(); if (ok) q.pop(); else q2.pop_back(); for(auto i : v[x]) { if(dpfn[a][b][i] > cost+1) { dpfn[a][b][i] = cost+1; q.push({dpfn[a][b][i], i}); } } } } void fn(int a, int b) { vector <pair <int, int>> q; for(int k = a; k < b; k++) for(int node = 1; node <= nd; node++) dpfn[a][b][node] = min(dpfn[a][b][node], dpfn[a][k][node] + dpfn[k+1][b][node]); for(int k = a; k < b; k++) for(int node = 1; node <= nd; node++) if(dpfn[a][b][node] != 1e9) q.push_back({dpfn[a][b][node], node}); sort(q.begin(), q.end(), greater<pair<int,int>>()); compute(a, b, q); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> w >> h; for(int i = 1; i <= h; i++) { for(int j = 1; j <= w; j++) { cin >> a[i][j]; mp[i][j] = ++nd; if(a[i][j] >= '1' and a[i][j] <= '9') ind[a[i][j] - '0'] = nd; } } for(int i = 1; i <= n; i++) { for(int i1 = 1; i1 <= n; i1++) { for(int i2 = 1; i2 <= nd; i2++) { dpfn[i][i1][i2] = 1e9; } } } v.resize(nd+1); for(int i = 1; i <= h; i++) { for(int j = 1; j <= w; j++) { for(int k = 0; k < 4; k++) { pair <int, int> ind = f(i, j, k); if(ind != pair <int, int> {i, j}) v[mp[i][j]].push_back(mp[ind.ff][ind.ss]); } } } vector <pair <int, int>> q; for(int i = 1; i <= n; i++) { dpfn[i][i][ind[i]] = 0; q.push_back({0, ind[i]}); compute(i, i, q); } for(int i = 0; i < n; i++) for(int a = 1; a + i <= n; a++) fn(a, a + i); int ans = 1e9; for(int i = 1; i <= nd; i++) ans = min(ans, dpfn[1][n][i]); cout << (ans == 1e9 ? -1 : ans) << "\n"; 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...