제출 #1165680

#제출 시각아이디문제언어결과실행 시간메모리
1165680Muhammet로봇 (APIO13_robots)C++20
0 / 100
2 ms4164 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define ll long long const int N = 305; char a[N][N]; int mp[N][N], n, w, h, ind[10], nd, dpfn[10][10][10005]; map <pair <int,int>, int> ds; pair <int, int> dp[N][N][4]; vector <int> dis; 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}; } int fn(int a, int b, int vn) { if(dpfn[a][b][vn] != -1) return dpfn[a][b][vn]; queue <int> q; dis.assign(nd+1, 1e9); q.push(vn); dis[vn] = 0; for(int i = 1; i <= nd; i++) { ds[{vn, i}] = 1e9; } ds[{vn, vn}] = 0; while(!q.empty()) { int x = q.front(); q.pop(); for(auto i : v[x]) { if(dis[i] > dis[x] + 1) { dis[i] = dis[x] + 1; ds[{vn, i}] = dis[i]; q.push(i); } } } if(a == b) return dpfn[a][b][vn] = dis[ind[a]]; 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) + ds[{v1, vn}]); } int y = 1e9; for(int v1 = 1; v1 <= nd; v1++) { y = min(y, fn(i+1, b, v1) + ds[{v1, vn}]); } ans = min(ans, x + y); } // cout << a << ' ' << b << ' ' << vn << ' ' << ans << "\n"; return dpfn[a][b][vn] = 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]); } } } 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...