제출 #364657

#제출 시각아이디문제언어결과실행 시간메모리
364657Nima_Naderi로봇 (APIO13_robots)C++14
60 / 100
1597 ms155876 KiB
///In the name of GOD //#pragma GCC optimize("O2") #include<bits/stdc++.h> using namespace std; typedef int ll; typedef pair<ll, ll> pll; const ll MXN = 500 + 2; const ll MXK = 12; const ll INF = 1e9; ll n, m, k; int dp[MXK][MXK][MXN][MXN]; pair<int, int> dest[MXN][MXN][4], Pr; vector<pair<ll, ll>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // R, D, L, U priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq; string s[MXN]; bool vis[MXN][MXN][4], ok[MXN][MXN][4]; bool mark[MXN][MXN]; bool check(ll x, ll y){ return (1 <= x && x <= n && 1 <= y && y <= m); } pair<int, int> go(ll x, ll y, ll d){ if(vis[x][y][d]) return {-1, -1}; if(ok[x][y][d]) return dest[x][y][d]; ll nd = d; if(s[x][y] == 'A') nd = (nd + 3) % 4; if(s[x][y] == 'C') nd = (nd + 1) % 4; ll dx, dy; tie(dx, dy) = dir[nd]; if(check(x + dx, y + dy) && s[x + dx][y + dy] != 'x'){ vis[x][y][d] = 1; dest[x][y][d] = go(x + dx, y + dy, nd); ok[x][y][d] = 1; vis[x][y][d] = 0; return dest[x][y][d]; } dest[x][y][d] = {x, y}; ok[x][y][d] = 1; return dest[x][y][d]; } void BFS(ll l, ll r){ pair<ll, ll> pr; while(!pq.empty()){ int d; tie(d, pr) = pq.top(); pq.pop(); ll x, y; tie(x, y) = pr; if(mark[x][y]) continue; mark[x][y] = 1; for(int dr = 0; dr < 4; dr ++){ ll xp, yp; tie(xp, yp) = dest[x][y][dr]; if(xp == -1 || yp == -1 || mark[xp][yp]) continue; if(d + 1 < dp[l][r][xp][yp]){ dp[l][r][xp][yp] = d + 1; Pr = make_pair(xp, yp); pq.push({dp[l][r][xp][yp], Pr}); } } } } int main(){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); memset(dest, -1, sizeof dest), memset(dp, 63, sizeof dp); cin >> k >> n >> m; swap(n, m); for(int i = 1; i <= n; i ++){ cin >> s[i]; s[i] = "$" + s[i]; } for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++){ if(s[i][j] == 'x') continue; for(int d = 0; d < 4; d ++) dest[i][j][d] = go(i, j, d); } } for(int i = 1; i <= k; i ++){ for(int x = 1; x <= n; x ++){ for(int y = 1; y <= m; y ++){ if(s[x][y] == char(i + '0')){ dp[i][i][x][y] = 0; } Pr = make_pair(x, y); pq.push({dp[i][i][x][y], Pr}); mark[x][y] = 0; } } BFS(i, i); } for(int len = 2; len <= k; len ++){ for(int l = 1, r = len; r <= k; l ++, r ++){ for(int x = 1; x <= n; x ++){ for(int y = 1; y <= m; y ++){ for(int mid = l; mid < r; mid ++){ dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][mid][x][y] + dp[mid + 1][r][x][y]); } Pr = make_pair(x, y); pq.push({dp[l][r][x][y], Pr}); mark[x][y] = 0; } } BFS(l, r); } } int ans = INF; for(int x = 1; x <= n; x ++){ for(int y = 1; y <= m; y ++){ ans = min(ans, dp[1][k][x][y]); } } cout << (ans == INF ? -1 : ans) << '\n'; return 0; } /*! HE'S AN INSTIGATOR, ENEMY ELIMINATOR, AND WHEN HE KNOCKS YOU BETTER YOU BETTER LET HIM IN. */ //! N.N
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...