#include <bits/stdc++.h>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 505, N2 = N * N;
typedef pair<int, int> ii;
int n, m, robots, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; //x is the row, y is the column
char dName[] = {'N', 'E', 'S', 'W'};
char a[N][N];
ii enPos[N][N][4];
int getClockwise(int dir) {
return (dir + 1) % 4;
}
int getAnti(int dir) {
return (dir + 3) % 4;
}
bool check(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] != 'x') return true;
return false;
}
ii getEnPos(int x, int y, int dir) {
if (enPos[x][y][dir] != ii(-1, -1)) return enPos[x][y][dir];
int ogDir = dir;
if (a[x][y] == 'A') dir = getAnti(dir);
if (a[x][y] == 'C') dir = getClockwise(dir);
if (!check(x + dx[dir], y + dy[dir])) return enPos[x][y][ogDir] = ii(x, y);
else return enPos[x][y][ogDir] = getEnPos(x + dx[dir], y + dy[dir], dir);
}
int getID(int x, int y) {
return x * m + y;
}
int getID(ii a) {
return a.fi * m + a.se;
}
vector<int> g[N2];
int dp[N2][10][10];
int solve(int l, int r) {
fw (i, 0, n * m) {
fw (mid, l, r) dp[i][l][r] = min(dp[i][l][r], dp[i][l][mid] + dp[i][mid + 1][r]);
}
//Now do some shitty ass BFS.
priority_queue<ii, vector<ii>, greater<ii>> pq;
fw (i, 0, n * m) if (dp[i][l][r] != inf) pq.push(ii(dp[i][l][r], i));
while (!pq.empty()) {
ii tmp = pq.top(); pq.pop();
int u = tmp.se;
if (tmp.fi != dp[u][l][r]) continue;
fa (v, g[u]) if (dp[u][l][r] + 1 < dp[v][l][r]) {
dp[v][l][r] = dp[u][l][r] + 1;
pq.push(ii(dp[v][l][r], v));
}
}
// fw (i, 0, n * m) if (dp[i][l][r] != inf) {
// cout << "dp[" << i << "][" << l << "][" << r << "] = " << dp[i][l][r] << "\n";
// }
}
signed main() {
#ifdef BLU
in("blu.inp");
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> robots >> m >> n;
fw (i, 0, n) fw (j, 0, m) {
cin >> a[i][j];
fw (k, 0, 4) enPos[i][j][k] = ii(-1, -1);
}
fw (i, 0, n) fw (j, 0, m) {
fw (dir, 0, 4) {
ii enPos = getEnPos(i, j, dir);
g[getID(i, j)].pb(getID(enPos));
}
}
fw (i, 0, n * m) fw (l, 0, robots) fw (r, l, robots) dp[i][l][r] = inf;
fw (i, 0, n) fw (j, 0, m) {
if (a[i][j] >= '1' && a[i][j] <= '9') {
int num = a[i][j] - '1';
// cout << "num = " << num << " getID = " << getID(i, j) << "\n";
dp[getID(i, j)][num][num] = 0;
}
}
fw (len, 1, robots + 1) {
fw (l, 0, robots) {
int r = l + len - 1;
if (r >= robots) break;
solve(l, r);
}
}
int ans = inf;
fw (i, 0, n * m) ans = min(ans, dp[i][0][robots - 1]);
cout << ans;
return 0;
}
Compilation message
robots.cpp: In function 'int solve(int, int)':
robots.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6272 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6272 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6272 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6272 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
