Submission #969997

#TimeUsernameProblemLanguageResultExecution timeMemory
969997Halym2007Robots (APIO13_robots)C++17
30 / 100
119 ms69720 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e2 + 5; #define ff first #define ss second #define pii pair <int, int> #define pb push_back char a[N][N]; queue <pii> q; // yokary saga asak cepe int aa[] = {-1, 0, 1, 0}; int bb[] = {0, 1, 0, -1}; int n, h, w, state[N][N][4], dis[N][N][10], dp[N][N][10][10]; bool vis[N][N][10]; pii val[N][N][4]; vector <pii> v[N]; pii ugur (int x, int y, int typ) { if (a[x][y] == 'A') typ--; else if (a[x][y] == 'C') typ++; typ += 4;typ %= 4; if (state[x][y][typ] == 2) return val[x][y][typ]; else if (state[x][y][typ] == 1) return {-1, -1}; state[x][y][typ] = 1; int new_x = x + aa[typ], new_y = y + bb[typ]; if (new_x < 1 or new_y < 1 or new_x > h or new_y > w or a[new_x][new_y] == 'x') val[x][y][typ] = {x, y}; else val[x][y][typ] = ugur (new_x, new_y, typ); state[x][y][typ] = 2; return val[x][y][typ]; } void solve (int x, int y, int typ) { dis[x][y][typ] = 0; vis[x][y][typ] = 1; q.push ({x, y}); while (!q.empty()) { pii a1 = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { pii tr = ugur (a1.ff, a1.ss, i); if (tr.ff != -1 and tr.ss != -1) { if (vis[tr.ff][tr.ss][typ]) continue; vis[tr.ff][tr.ss][typ] = 1; dis[tr.ff][tr.ss][typ] = dis[a1.ff][a1.ss][typ] + 1; q.push({tr.ff, tr.ss}); } } } } int main () { ios::sync_with_stdio(0);cin.tie(0); // freopen ("input.txt", "r", stdin); cin >> n >> w >> h; for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { cin >> a[i][j]; } } for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { for (int k = 1; k <= n; ++k) { dis[i][j][k] = 1e9; } } } for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { if (a[i][j] >= '1' and a[i][j] <= '9') { dis[i][j][int(a[i][j] - 48)] = 0; solve (i, j, int(a[i][j] - 48)); } } } for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { for (int l = 1; l <= h; ++l) { for (int r = 1; r <= w; ++r) { dp[l][r][i][j] = 1e9; } } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j + i - 1 <= n; ++j) { int git = j + i - 1; if (i == 1) { for (int l = 1; l <= h; ++l) { for (int r = 1; r <= w; ++r) { dp[l][r][j][j] = dis[l][r][j]; } } continue; } // tapmaly dp[l][r][j][git] for (int k = 0; k < N; ++k) v[i].clear(); for (int l = 1; l <= h; ++l) { for (int r = 1; r <= w; ++r) { for (int k = j; k < git; ++k) { int sym = dp[l][r][j][k] + dp[l][r][k + 1][git]; dp[l][r][j][git] = min (dp[l][r][j][git], sym); if (sym < N) v[sym].pb ({l, r}); } } } for (int k = 1; k < N; ++k) { for (pii x : v[k]) { for (int l = 0; l < 4; ++l) { pii new_x = ugur (x.ff, x.ss, l); if (new_x.ff != -1 and new_x.ss != -1) { if (k > dp[new_x.ff][new_x.ss][j][git] + 1) { dp[x.ff][x.ss][j][git] = min (dp[x.ff][x.ss][j][git], dp[new_x.ff][new_x.ss][j][git] + 1); } } } } } } } int jogap = 1e9; for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { jogap = min (jogap, dp[i][j][1][n]); } } if (jogap == 1e9) jogap = -1; cout << jogap; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...