#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 500, MAXM = 500, MAXD = 9;
const int INF = (1 << 25);
char board[MAXN][MAXM];
int dp[MAXN][MAXM][MAXD][MAXD];
int dd[MAXN][MAXM];
pii f[MAXN][MAXM][4];
pii pos[MAXD];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int d, n, m;
bool in(int i, int j){
return 0 <= i && i < n && 0 <= j && j < m && board[i][j] != 'x';
}
bool vis[MAXN][MAXM][4];
pii dfs(int i, int j, int dir){
if(vis[i][j][dir]) return {-1, -1};
if(f[i][j][dir].fi != -2) return f[i][j][dir];
vis[i][j][dir] = true;
if(!in(i + dx[dir], j + dy[dir])){
f[i][j][dir] = {i, j};
vis[i][j][dir] = false;
return {i, j};
}
f[i][j][dir] = dfs(i + dx[dir], j + dy[dir], (dir + dd[i + dx[dir]][j + dy[dir]] + 4) % 4);
vis[i][j][dir] = false;
return f[i][j][dir];
}
struct CMP{
bool operator()(pair<pii, pii> a, pair<pii, pii> b){
return a.fi.se < b.fi.se || a.fi.se == b.fi.se && a.fi.fi > b.fi.fi;
}
};
int main(){
cin >> d >> m >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> board[i][j];
if(board[i][j] >= '0' && board[i][j] <= '9') pos[board[i][j] - '1'] = {i, j}, board[i][j] = '.';
if(board[i][j] == 'C') dd[i][j] = 1;
if(board[i][j] == 'A') dd[i][j] = -1;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int dir = 0; dir < 4; dir++){
f[i][j][dir].fi = -2;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int dir = 0; dir < 4; dir++){
if(f[i][j][dir].fi == -2) dfs(i, j, dir);
}
}
}
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// for(int k = 0; k < 4; k++){
// cout << i << ' ' << j << ' ' << k << ' ' << f[i][j][k].fi << ' ' << f[i][j][k].se << endl;
// }
// }
// }
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int d1 = 0; d1 < d; d1++){
for(int d2 = d1; d2 < d; d2++){
dp[i][j][d1][d2] = INF;
}
}
}
}
priority_queue<pair<pii, pii>, vector<pair<pii, pii>>, CMP> q;
for(int i = 0; i < d; i++){
for(int j = i; j >= 1; j--){
q.push({{dp[pos[i].fi][pos[i].se][j - 1][i - 1], j - 1}, pos[i]});
}
q.push({{0, i}, pos[i]});
while(!q.empty()){
pair<pii, pii> v = q.top(); q.pop();
int cost = v.fi.fi, nd = v.fi.se, x = v.se.fi, y = v.se.se;
dp[x][y][nd][i] = cost;
for(int dir = 0; dir < 4; dir++){
int nx = f[x][y][dir].fi, ny = f[x][y][dir].se;
if(nx == x && ny == y) continue;
int co = cost + 1;
if(co >= dp[nx][ny][nd][i]) continue;
q.push({{co, nd}, {nx, ny}});
for(int j = nd; j >= 1; j--){
if(co + dp[nx][ny][j - 1][nd - 1] >= dp[nx][ny][j - 1][i]) continue;
dp[nx][ny][j - 1][i] = co + dp[nx][ny][j - 1][nd - 1];
q.push({{co + dp[nx][ny][j - 1][nd - 1], j - 1}, {nx, ny}});
}
}
}
}
int ans = INF;
// for(int d1 = 0; d1 < d; d1++){
// for(int d2 = d1; d2 < d; d2++){
// cout << "d " << d1 << ' ' << d2 << endl;
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// cout << (dp[i][j][d1][d2] >= INF ? -1 : dp[i][j][d1][d2]) << ' ';
// }
// cout << endl;
// }
// }
// }
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
ans = min(ans, dp[i][j][0][d - 1]);
}
}
cout << (ans >= INF ? -1 : ans) << endl;
}
Compilation message
robots.cpp: In member function 'bool CMP::operator()(std::pair<std::pair<int, int>, std::pair<int, int> >, std::pair<std::pair<int, int>, std::pair<int, int> >)':
robots.cpp:40:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
40 | return a.fi.se < b.fi.se || a.fi.se == b.fi.se && a.fi.fi > b.fi.fi;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
