#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;
const int N = 510, MAX_COST = 500 * 75 * 9 + 2, oo = 2000000000;
char grid[N][N];
int n, m, k, dp[50][N][N], hsh[10][10], hashcnt = 0;
pair<int, int> go[4][N][N];
int dr[4] = { 0,1,0,-1 };
int dc[4] = { 1,0,-1,0 };
string shp[5] = { "right","down","left","up" };
struct S {
int r, c, low, high;
S(int a, int b, int e, int d) { r = a, c = b, low = e, high = d; }
};
vector< S > pq[MAX_COST];
inline bool cangoto(int r, int c) {
return (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != '#');
}
void make(int r, int c, int d) {
int sr = r, sc = c;
while (cangoto(r, c)) {
go[d][r][c] = make_pair(sr, sc);
if (grid[r][c] == 'C') d--; else if (grid[r][c] == 'A') d++;
if (d == 4) d = 0;
if (d == -1) d = 3;
r += dr[d];
c += dc[d];
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
memset(dp, -1, sizeof(dp));
for (int i = 1;i <= 9;i++) {
for (int j = i;j <= 9;j++) {
hsh[i][j] = hashcnt++;
}
}
memset(go, -1, sizeof(go));
scanf("%d%d%d", &k, &m, &n);
for (int i = 0;i < n;i++)
scanf("%s", grid[i]);
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
if (grid[i][j] >= '1' && grid[i][j] <= '9') {
pq[0].push_back(S(i, j, grid[i][j] - '0', grid[i][j] - '0'));
}
if (grid[i][j] == 'x') continue;
for (int k = 0;k < 4;k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if (cangoto(nr, nc) == false) {
make(i, j, (k + 2) % 4);
}
}
}
}
int low, high, r, c, nr, nc, ans = oo;
for (int i = 0;i < MAX_COST - 1;i++) {
for (int j = 0;j < (int)pq[i].size();j++) {
r = pq[i][j].r;
c = pq[i][j].c;
low = pq[i][j].low;
high = pq[i][j].high;
if (dp[hsh[low][high]][r][c] != -1)
continue;
if (low == 1 && high == k)
ans = min(ans, i);
dp[hsh[low][high]][r][c] = i;
for (int j = 0;j < 4;j++) {
nr = go[j][r][c].first;
nc = go[j][r][c].second;
if (dp[hsh[low][high]][nr][nc] == -1)
pq[i + 1].push_back(S(nr, nc, low, high));
}
for (int j = low - 1;j >= 1;j--) {
if (dp[hsh[j][low - 1]][r][c] != -1 && dp[hsh[j][high]][r][c] == -1)
pq[i + dp[hsh[j][low - 1]][r][c]].push_back(S(r, c, j, high));
}
for (int j = high + 1;j <= k;j++) {
if (dp[hsh[high + 1][j]][r][c] != -1 && dp[hsh[low][j]][r][c] == -1)
pq[i + dp[hsh[high + 1][j]][r][c]].push_back(S(r, c, low, j));
}
}
}
if (ans == oo) ans = -1;
printf("%d\n", ans);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:47:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &k, &m, &n);
^
robots.cpp:49:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", grid[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
67192 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
67296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
67192 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
67296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
67192 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
67296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
67192 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
67296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
