#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 500;
int dp[N][N][9][9];
char grid[N][N];
int rows, cols, n;
bool is_valid(int x, int y){
return (x < cols && x >= 0 && y < rows && y >= 0 && grid[y][x] != 'x');
}
//void dfs_all(int x, int y, int start, int end, int dist){
// for (int dir = 0; dir < 4; dir++){
// int dx=0, dy=0;
// if (dir == 0) dx = -1;
// if (dir == 1) dy = 1;
// if (dir == 2) dx = 1;
// if (dir == 3) dy = -1;
// if (is_valid(x+dx, y+dy)){
// bfs(x, y, start, end, dir, dist+1);
// }
// }
//}
void bfs(int x, int y, int start, int end, int dist, int dir){
if (!is_valid(x, y)) return;
if (grid[y][x] == 'A'){
dir+=1;
dir=(dir%4);
}
else if(grid[y][x] == 'C'){
dir+=3;
dir=(dir%4);
}
int dx=0, dy=0;
if (dir == 0) dx = -1;
if (dir == 1) dy = 1;
if (dir == 2) dx = 1;
if (dir == 3) dy = -1;
if (is_valid(x+dx, y+dy)){
bfs(x+dx, y+dy, start, end, dist, dir);
}
else{
if (dp[y][x][start][end] == -1 || dp[y][x][start][end] > dist) {
dp[y][x][start][end] = dist;
bfs(x-1, y, start, end, dp[y][x][start][end]+1, 0);
bfs(x, y+1, start, end, dp[y][x][start][end]+1, 1);
bfs(x+1, y, start, end, dp[y][x][start][end]+1, 2);
bfs(x, y-1, start, end, dp[y][x][start][end]+1, 3);
int r1 = start-1;
for (int l1 = 0; l1 < start; l1++){
if (dp[y][x][l1][r1] != -1 && (dp[y][x][l1][end] == -1 || dp[y][x][l1][end] > dp[y][x][l1][r1]+dist)){
dp[y][x][l1][end] = dist+dp[y][x][l1][r1];
bfs(x-1, y, l1, end, dp[y][x][l1][end]+1, 0);
bfs(x, y+1, l1, end, dp[y][x][l1][end]+1, 1);
bfs(x+1, y, l1, end, dp[y][x][l1][end]+1, 2);
bfs(x, y-1, l1, end, dp[y][x][l1][end]+1, 3);
}
}
int l2 = end+1;
for (int r2 = end+1; r2 < n; r2++){
if (dp[y][x][l2][r2] != -1 && (dp[y][x][end][r2] == -1 || dp[y][x][end][r2] > dp[y][x][l2][r2]+dist)){
dp[y][x][start][r2] = dist+dp[y][x][l2][r2];
bfs(x-1, y, start, r2, dp[y][x][start][r2]+1, 0);
bfs(x, y+1, start, r2, dp[y][x][start][r2]+1, 1);
bfs(x+1, y, start, r2, dp[y][x][start][r2]+1, 2);
bfs(x, y-1, start, r2, dp[y][x][start][r2]+1, 3);
}
}
for (int l1 = 0; l1 < start; l1++){
for (int r2 = end+1; r2 < n; r2++){
if (dp[y][x][l1][start] != -1 && dp[y][x][end][r2] != -1 && (dp[y][x][l1][r2] == -1 || dp[y][x][l1][r2] > dp[y][x][l1][start]+dp[y][x][end][r2]+dist)){
dp[y][x][l1][r2] = dp[y][x][l1][start]+dp[y][x][end][r2]+dist;
bfs(x-1, y, l1, r2, dp[y][x][l1][r2]+1, 0);
bfs(x, y+1, l1, r2, dp[y][x][l1][r2]+1, 1);
bfs(x+1, y, l1, r2, dp[y][x][l1][r2]+1, 2);
bfs(x, y-1, l1, r2, dp[y][x][l1][r2]+1, 3);
}
}
}
}
}
}
void solve(){
memset(dp, -1, sizeof(dp));
cin >> n >> cols >> rows;
for (int y = 0; y < rows; y++){
for (int x = 0; x < cols; x++){
cin >> grid[y][x];
if ( (grid[y][x]-'0') >= 1 && (grid[y][x]-'0') <= 9){
int dig = (grid[y][x]-'0')-1;
dp[y][x][dig][dig] = 0;
}
}
}
for (int y = 0; y < rows; y++){
for (int x = 0; x < cols; x++){
if (grid[y][x]-'0' >= 1 && grid[y][x]-'0' <= 9){
int dig = (grid[y][x]-'0')-1;
bfs(x-1, y, dig, dig, 1, 0);
bfs(x, y+1, dig, dig, 1, 1);
bfs(x+1, y, dig, dig, 1, 2);
bfs(x, y-1, dig, dig, 1, 3);
}
}
}
bool ok = false;
int ans = INFINITY;
for (int y = 0; y < rows; y++){
for (int x = 0; x < cols; x++){
if (dp[y][x][0][n-1] != -1){
ans = min(ans, dp[y][x][0][n-1]);
ok = true;
}
}
}
if (ok){
cout << ans << endl;
}
else{
cout << -1 << endl;
}
}
int main() {
fast;
int t = 1;
while (t--){
solve();
}
return 0;
}
Compilation message
robots.cpp: In function 'void solve()':
robots.cpp:125:15: warning: overflow in conversion from 'float' to 'int' changes value from '+Inff' to '2147483647' [-Woverflow]
125 | int ans = INFINITY;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
79572 KB |
Output is correct |
| 2 |
Correct |
29 ms |
79556 KB |
Output is correct |
| 3 |
Correct |
29 ms |
79508 KB |
Output is correct |
| 4 |
Correct |
33 ms |
79552 KB |
Output is correct |
| 5 |
Correct |
29 ms |
79548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
79572 KB |
Output is correct |
| 2 |
Correct |
29 ms |
79556 KB |
Output is correct |
| 3 |
Correct |
29 ms |
79508 KB |
Output is correct |
| 4 |
Correct |
33 ms |
79552 KB |
Output is correct |
| 5 |
Correct |
29 ms |
79548 KB |
Output is correct |
| 6 |
Correct |
29 ms |
79452 KB |
Output is correct |
| 7 |
Correct |
29 ms |
79572 KB |
Output is correct |
| 8 |
Correct |
30 ms |
79468 KB |
Output is correct |
| 9 |
Correct |
29 ms |
79568 KB |
Output is correct |
| 10 |
Correct |
29 ms |
79624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
79572 KB |
Output is correct |
| 2 |
Correct |
29 ms |
79556 KB |
Output is correct |
| 3 |
Correct |
29 ms |
79508 KB |
Output is correct |
| 4 |
Correct |
33 ms |
79552 KB |
Output is correct |
| 5 |
Correct |
29 ms |
79548 KB |
Output is correct |
| 6 |
Correct |
29 ms |
79452 KB |
Output is correct |
| 7 |
Correct |
29 ms |
79572 KB |
Output is correct |
| 8 |
Correct |
30 ms |
79468 KB |
Output is correct |
| 9 |
Correct |
29 ms |
79568 KB |
Output is correct |
| 10 |
Correct |
29 ms |
79624 KB |
Output is correct |
| 11 |
Execution timed out |
1577 ms |
90720 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
79572 KB |
Output is correct |
| 2 |
Correct |
29 ms |
79556 KB |
Output is correct |
| 3 |
Correct |
29 ms |
79508 KB |
Output is correct |
| 4 |
Correct |
33 ms |
79552 KB |
Output is correct |
| 5 |
Correct |
29 ms |
79548 KB |
Output is correct |
| 6 |
Correct |
29 ms |
79452 KB |
Output is correct |
| 7 |
Correct |
29 ms |
79572 KB |
Output is correct |
| 8 |
Correct |
30 ms |
79468 KB |
Output is correct |
| 9 |
Correct |
29 ms |
79568 KB |
Output is correct |
| 10 |
Correct |
29 ms |
79624 KB |
Output is correct |
| 11 |
Execution timed out |
1577 ms |
90720 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
