#include "bits/stdc++.h"
using namespace std;
using pii = pair <int, int>;
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0};
pii dp[4][505][505];
bool vis[4][505][505];
char s[505][505];
int n, m;
int opt[10][10][505][505];
const int inf = 1e9;
struct data {
int x, y, cost;
data (int x, int y, int cost) : x(x), y(y), cost(cost) {}
data () {}
bool operator < (data d) const {
return cost > d.cost;
}
};
bool inside(int x, int y) {
return (0 <= x && x < n) && (0 <= y && y < m);
}
pii func(int d, int x, int y) {
if(vis[d][x][y] == true) return dp[d][x][y];
vis[d][x][y] = true;
int nd = d;
if(s[x][y] == 'A') nd = (d + 1) % 4;
if(s[x][y] == 'C') nd = (d + 3) % 4;
int nx = x + dx[nd];
int ny = y + dy[nd];
if(inside(nx, ny) && s[nx][ny] != 'x') {
dp[d][x][y] = func(nd, nx, ny);
} else {
dp[d][x][y] = pii(x, y);
}
return dp[d][x][y];
}
void propagate(int l, int r) {
priority_queue <data> Q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
Q.emplace(i, j, opt[l][r][i][j]);
}
}
while(!Q.empty()) {
data p = Q.top();
Q.pop();
for(int d = 0; d < 4; d++) {
pii q = func(d, p.x, p.y);
if(q.first == -1) continue;
int &ret = opt[l][r][q.first][q.second];
if(ret > opt[l][r][p.x][p.y] + 1) {
ret = opt[l][r][p.x][p.y] + 1;
Q.emplace(q.first, q.second, ret);
}
}
}
return ;
}
int main(int argc, char const *argv[])
{
int N;
scanf("%d %d %d", &N, &n, &m);
swap(n, m);
for(int i = 0; i < n; i++) {
scanf("%s", s[i]);
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
for(int d = 0; d < 4; d++) {
dp[d][i][j] = pii(-1, -1);
vis[d][i][j] = false;
}
}
}
for(int i = 1; i <= N; i++) {
for(int j = i; j <= N; j++) {
for(int x = 0; x < n; x++) {
for(int y = 0; y < m; y++) {
opt[i][j][x][y] = inf;
}
}
}
}
for(int x = 0; x < n; x++) {
for(int y = 0; y < m; y++) {
if(isdigit(s[x][y])) {
int c = s[x][y] - '0';
opt[c][c][x][y] = 0;
propagate(c, c);
}
}
}
for(int sz = 2; sz <= N; sz++) {
for(int i = 1; i <= N - sz + 1; i++) {
int j = i + sz - 1;
for(int x = 0; x < n; x++) {
for(int y = 0; y < m; y++) {
for(int k = i; k < j; k++) {
opt[i][j][x][y] = min(opt[i][j][x][y], opt[i][k][x][y] + opt[k + 1][j][x][y]);
}
}
}
propagate(i, j);
}
}
int ans = inf;
for(int x = 0; x < n; x++) for(int y = 0; y < m; y++) ans = min(ans, opt[1][N][x][y]);
printf("%d\n", ans);
return 0;
}
Compilation message
robots.cpp: In function 'int main(int, const char**)':
robots.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
