| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 477931 |
2021-10-04T15:57:55 Z |
jungsnow |
Robots (APIO13_robots) |
C++14 |
|
42 ms |
98484 KB |
#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
/// 0 - R, 1 - L, 2 - D, 3 - U
const int N = 501;
const int oo = 1e9;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
int n, w, h;
bool stop[N][N];
int dp[10][10][N][N];
char a[N][N];
ii pos[10];
ii lst[N][N][4];
bool ok(int x, int y) {
if (x < 1 || y < 1 || x > h || y > w) return 0;
if (a[x][y] == 'x') return 0;
return 1;
}
bool dig(int x, int y) {
return (a[x][y] >= '1' && a[x][y] <= '9');
}
/// 0 - R, 1 - L, 2 - D, 3 - U
int A(int dir) { /// ccw
if (dir == 0) return 3;
else if (dir == 1) return 2;
else if (dir == 2) return 0;
else if (dir == 3) return 1;
}
int C(int dir) { /// cw
if (dir == 0) return 2;
else if (dir == 1) return 3;
else if (dir == 2) return 1;
else if (dir == 3) return 0;
}
void dfs(int i, int j, int dir) {
if (lst[i][j][dir].x != -1) return;
if (a[i][j] == 'C') dir = C(dir);
else if (a[i][j] == 'A') dir = A(dir);
int ni = i + dx[dir];
int nj = j + dy[dir];
if (!ok(ni, nj)) {
stop[i][j] = 1;
lst[i][j][dir] = {i, j};
for (int k = 0; k < 4; k++) if (k != dir) {
ni = i + dx[k];
nj = j + dy[k];
if (ok(ni, nj)) {
dfs(ni, nj, k);
lst[i][j][k] = lst[ni][nj][k];
} else {
lst[i][j][k] = {i, j};
}
}
}
else {
dfs(ni, nj, dir);
lst[i][j][dir] = lst[ni][nj][dir];
}
}
int main() {
// freopen("cc.inp", "r", stdin);
// freopen("cc.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> w >> h;
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> a[i][j];
if (dig(i, j)) {
pos[a[i][j] - '0'].x = i;
pos[a[i][j] - '0'].y = j;
}
}
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int dir = 0; dir < 4; dir++) {
lst[i][j][dir] = {-1, -1};
}
}
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) for (int k = 0; k < 4; k++) {
dfs(i, j, k);
}
}
deque<ii> q;
for (int i = 1; i <= n; i++) {
int x = pos[i].x;
int y = pos[i].y;
while (q.size()) q.pop_front();
q.push_back({x, y});
dp[i][i][x][y] = 0;
while (q.size()) {
ii cur = q.front();
q.pop_front();
x = cur.x;
y = cur.y;
for (int j = 0; j < 4; j++) {
int nx = lst[x][y][j].x;
int ny = lst[x][y][j].y;
if (ok(nx, ny) && dp[i][i][nx][ny] > dp[i][i][x][y] + 1) {
dp[i][i][nx][ny] = dp[i][i][x][y] + 1;
q.push_back({nx, ny});
}
}
}
}
queue<ii> qq;
for (int l = n - 1; l >= 1; l--) {
for (int r = l + 1; r <= n; r++) {
vector<iii> v;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
for (int k = l; k < r; k++) {
dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][k][i][j] + dp[k + 1][r][i][j]);
}
}
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (dp[l][r][i][j] < 1e9)
v.push_back(iii(dp[l][r][i][j], {i, j}));
}
}
while (q.size()) q.pop_back();
while (qq.size()) qq.pop();
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) {
q.push_back({v[i].y.x, v[i].y.y});
}
while (q.size()) {
ii cur = q.front();
q.pop_front();
int x = cur.x;
int y = cur.y;
#define q2 qq
q2.push({x, y});
int tm = dp[l][r][x][y];
while (q.size()) {
int nx = q.front().x;
int ny = q.front().y;
if (dp[l][r][nx][ny] != tm) break;
q.pop_front();
q2.push({nx, ny});
}
while (q2.size()) {
cur = q2.front();
q2.pop();
x = cur.x;
y = cur.y;
if (!stop[x][y]) continue;
for (int dir = 0; dir < 4; dir++) {
int nx = lst[x][y][dir].x;
int ny = lst[x][y][dir].y;
if (!ok(nx, ny)) continue;
if (dp[l][r][nx][ny] > dp[l][r][x][y] + 1) {
dp[l][r][nx][ny] = dp[l][r][x][y] + 1;
q.push_front({nx, ny});
}
}
}
}
}
}
int ans = 1e9;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) if (stop[i][j]) {
ans = min(ans, dp[1][n][i][j]);
}
}
cout << ans;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:156:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
robots.cpp: In function 'int A(int)':
robots.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
41 | }
| ^
robots.cpp: In function 'int C(int)':
robots.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
48 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
98452 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
98484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
98452 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
98484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
98452 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
98484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
98452 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
98484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
