| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 477937 |
2021-10-04T17:08:16 Z |
jungsnow |
Robots (APIO13_robots) |
C++14 |
|
44 ms |
98500 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}, dy[] = {1, -1, 0, 0};
const int maxn = 501, INF = 1e9;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
int N, W, H;
int dp[10][10][maxn][maxn];
char A[maxn][maxn];
bool stop[maxn][maxn];
ii pos[10], lst[maxn][maxn][4];
void minn(int &a, int b) {
if (a > b) a = b;
}
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');
}
int a[] = {3, 2, 0, 1};
int c[] = {2, 3, 1, 0};
void dfs(int i, int j, int dir) {
if (lst[i][j][dir].x != -1) return;
int ol = dir;
if (A[i][j] == 'C') dir = c[dir];
if (A[i][j] == 'A') dir = a[dir];
int ni = i + dx[dir], nj = j + dy[dir];
if (!ok(ni, nj)) {
stop[i][j] = 1;
lst[i][j][ol] = {i, j};
} else {
dfs(ni, nj, dir);
lst[i][j][ol] = lst[ni][nj][dir];
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen("mrobot.inp", "r", stdin);
freopen("mrobot.out", "w", stdout);
cin >> N >> W >> H;
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 dir = 0; dir < 4; ++dir) {
dfs(i, j, dir);
}
}
}
memset(dp, 0x3f, sizeof dp);
deque<ii> q;
for (int i = 1; i <= N; ++i) {
int x = pos[i].x, y = pos[i].y;
q.push_back({x, y});
dp[i][i][x][y] = 0;
while (q.size()) {
ii cur = q.front(); q.pop_front();
tie(x, y) = cur;
for (int j = 0; j < 4; ++j) {
int nx, ny;
tie(nx, ny) = lst[x][y][j];
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> q2;
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)
minn(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] < INF && stop[i][j])
v.push_back({dp[l][r][i][j], ii(i, j)});
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, y = cur.y;
int tm = dp[l][r][x][y];
q2.push({x, y});
while (q.size()) {
int nx, ny;
tie(nx, ny) = q.front();
if (dp[l][r][nx][ny] != tm) break;
q.pop_front();
q2.push({nx, ny});
}
while (q2.size()) {
cur = q2.front(); q2.pop();
int x = cur.x, y = cur.y;
if (!stop[x][y]) continue;
for (int k = 0; k < 4; ++k) {
int nx, ny;
tie(nx, ny) = lst[x][y][k];
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 = INF;
for (int i = 1; i <= H; ++i)
for (int j = 1; j <= W; ++j)
if (stop[i][j]) minn(ans, dp[1][N][i][j]);
if (ans == INF) ans = -1;
cout<<ans<<'\n';
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:113:25: 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]
113 | for (int i = 0; i < v.size(); ++i)
| ~~^~~~~~~~~~
robots.cpp:55:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | freopen("mrobot.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | freopen("mrobot.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
