Submission #1165566

#TimeUsernameProblemLanguageResultExecution timeMemory
1165566MuhammetRobots (APIO13_robots)C++20
30 / 100
108 ms229376 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]; pair <int, int> dp[N][N][4]; vector <vector <int>> v, dis; 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}; } int fn(int a, int b, int v) { if(dpfn[a][b][v] != -1) return dpfn[a][b][v]; if(a == b) return dis[ind[a]][v]; int ans = 1e9; for(int i = a; i < b; i++) { int x = 1e9; for(int v1 = 1; v1 <= nd; v1++) { x = min(x, fn(a, i, v1) + dis[v1][v]); } int y = 1e9; for(int v1 = 1; v1 <= nd; v1++) { y = min(y, fn(i+1, b, v1) + dis[v1][v]); } ans = min(ans, x + y); } return dpfn[a][b][v] = ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> w >> h; memset(dpfn, -1, sizeof dpfn); 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; } } 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]); } } } dis.assign(nd+1, vector <int> (nd+1, 1e9)); queue <int> q; for(int k = 1; k <= nd; k++) { q.push(k); dis[k][k] = 0; while(!q.empty()) { int x = q.front(); q.pop(); for(auto i : v[x]) { if(dis[k][i] == 1e9) { dis[k][i] = dis[k][x] + 1; q.push(i); } } } } int ans = 1e9; for(int i = 1; i <= nd; i++) { ans = min(ans, fn(1, n, i)); } cout << (ans == 1e9 ? -1 : ans); 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...