| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 915707 |
2024-01-24T15:17:59 Z |
Alcabel |
Robots (APIO13_robots) |
C++17 |
|
1500 ms |
163840 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxc = 500, maxn = 9;
const int deltaX[4] = {0, -1, 0, 1}, deltaY[4] = {1, 0, -1, 0};
char t[maxc][maxc];
pair<int, int> dest[maxc][maxc][4];
char vis[maxc][maxc][4];
int w, h;
pair<int, int> getDest(int x, int y, int dir) {
if (vis[x][y][dir] == 1) {
dest[x][y][dir] = {-1, -1};
return {-1, -1};
}
if (vis[x][y][dir] == 2) {
return dest[x][y][dir];
}
vis[x][y][dir] = 1;
int newDir = dir;
if (t[x][y] == 'A') {
newDir = (dir < 3 ? dir + 1 : 0);
} else if (t[x][y] == 'C') {
newDir = (dir > 0 ? dir - 1 : 3);
}
int newX = x + deltaX[newDir], newY = y + deltaY[newDir];
if (newX < 0 || newX >= h || newY < 0 || newY >= w || t[newX][newY] == 'x') {
dest[x][y][dir] = {x, y};
} else {
dest[x][y][dir] = getDest(newX, newY, newDir);
}
vis[x][y][dir] = 2;
return dest[x][y][dir];
}
const int inf = 1e9;
int dist[maxc][maxc];
int dp[maxn][maxn][maxc][maxc];
void bfs(int sx, int sy) {
static queue<pair<int, int>> q;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
dist[i][j] = -1;
}
}
dist[sx][sy] = 0;
q.emplace(sx, sy);
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; ++dir) {
auto [newX, newY] = dest[x][y][dir];
if (newX != -1 && dist[newX][newY] == -1) {
dist[newX][newY] = dist[x][y] + 1;
q.emplace(newX, newY);
}
}
}
int num = t[sx][sy] - '1';
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (dist[i][j] != -1) {
dp[num][num][i][j] = dist[i][j];
}
}
}
}
const int maxd = maxn * maxc * maxc + 10;
vector<pair<char, char>> byDist[maxd];
int distT[maxd], tt;
void solve() {
int n;
cin >> n >> w >> h;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> t[i][j];
}
}
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
// cerr << "i: " << i << ", j: " << j << '\n';
for (int dir = 0; dir < 4; ++dir) {
if (t[i][j] == 'x') {
dest[i][j][dir] = {-1, -1};
vis[i][j][dir] = 2;
} else {
dest[i][j][dir] = getDest(i, j, dir);
}
// cerr << "dir: " << dir << ", dest: " << dest[i][j][dir].first << ' ' << dest[i][j][dir].second << '\n';
}
}
}
for (int l = 0; l < n; ++l) {
for (int r = 0; r < n; ++r) {
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
dp[l][r][i][j] = inf;
}
}
}
}
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (t[i][j] >= '1' && t[i][j] <= '9') {
bfs(i, j);
}
}
}
tt = 0;
for (int len = 2; len <= n; ++len) {
for (int l = 0; l + len <= n; ++l) {
int r = l + len - 1;
// cerr << "l: " << l << ", r: " << r << '\n';
int needcnt = 0, start = inf;
++tt;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
for (int m = l; m < r; ++m) {
dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][m][i][j] + dp[m + 1][r][i][j]);
}
dist[i][j] = dp[l][r][i][j];
if (dist[i][j] != inf) {
++needcnt;
if (distT[dist[i][j]] < tt) {
distT[dist[i][j]] = tt;
byDist[dist[i][j]].clear();
}
byDist[dist[i][j]].emplace_back(i, j);
start = min(start, dist[i][j]);
}
// cerr << "i: " << i << ", j: " << j << ", dist: " << dist[i][j] << '\n';
}
}
while (needcnt > 0) {
while (start < maxd && distT[start] < tt) {
distT[start] = tt;
byDist[start].clear();
++start;
}
assert(start < maxd);
while (!byDist[start].empty()) {
auto [i, j] = byDist[start].back();
byDist[start].pop_back();
dp[l][r][i][j] = dist[i][j];
--needcnt;
for (int dir = 0; dir < 4; ++dir) {
auto [newI, newJ] = dest[i][j][dir];
if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) {
++needcnt;
int newd = dist[i][j] + 1;
dist[newI][newJ] = newd;
if (distT[newd] < tt) {
distT[newd] = tt;
byDist[newd].clear();
}
byDist[newd].emplace_back(newI, newJ);
}
}
}
++start;
}
}
}
int ans = inf;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ans = min(ans, dp[0][n - 1][i][j]);
}
}
if (ans == inf) {
ans = -1;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
Compilation message
robots.cpp: In function 'void solve()':
robots.cpp:147:30: warning: array subscript has type 'char' [-Wchar-subscripts]
147 | dp[l][r][i][j] = dist[i][j];
| ^
robots.cpp:147:33: warning: array subscript has type 'char' [-Wchar-subscripts]
147 | dp[l][r][i][j] = dist[i][j];
| ^
robots.cpp:147:43: warning: array subscript has type 'char' [-Wchar-subscripts]
147 | dp[l][r][i][j] = dist[i][j];
| ^
robots.cpp:147:46: warning: array subscript has type 'char' [-Wchar-subscripts]
147 | dp[l][r][i][j] = dist[i][j];
| ^
robots.cpp:150:50: warning: array subscript has type 'char' [-Wchar-subscripts]
150 | auto [newI, newJ] = dest[i][j][dir];
| ^
robots.cpp:150:53: warning: array subscript has type 'char' [-Wchar-subscripts]
150 | auto [newI, newJ] = dest[i][j][dir];
| ^
robots.cpp:151:67: warning: array subscript has type 'char' [-Wchar-subscripts]
151 | if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) {
| ^
robots.cpp:151:70: warning: array subscript has type 'char' [-Wchar-subscripts]
151 | if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) {
| ^
robots.cpp:153:45: warning: array subscript has type 'char' [-Wchar-subscripts]
153 | int newd = dist[i][j] + 1;
| ^
robots.cpp:153:48: warning: array subscript has type 'char' [-Wchar-subscripts]
153 | int newd = dist[i][j] + 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
61784 KB |
Output is correct |
| 2 |
Correct |
18 ms |
62044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 4 |
Correct |
17 ms |
62028 KB |
Output is correct |
| 5 |
Correct |
20 ms |
61788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
61784 KB |
Output is correct |
| 2 |
Correct |
18 ms |
62044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 4 |
Correct |
17 ms |
62028 KB |
Output is correct |
| 5 |
Correct |
20 ms |
61788 KB |
Output is correct |
| 6 |
Correct |
19 ms |
61788 KB |
Output is correct |
| 7 |
Correct |
17 ms |
61788 KB |
Output is correct |
| 8 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 9 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 10 |
Correct |
18 ms |
62024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
61784 KB |
Output is correct |
| 2 |
Correct |
18 ms |
62044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 4 |
Correct |
17 ms |
62028 KB |
Output is correct |
| 5 |
Correct |
20 ms |
61788 KB |
Output is correct |
| 6 |
Correct |
19 ms |
61788 KB |
Output is correct |
| 7 |
Correct |
17 ms |
61788 KB |
Output is correct |
| 8 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 9 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 10 |
Correct |
18 ms |
62024 KB |
Output is correct |
| 11 |
Execution timed out |
2173 ms |
163840 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
61784 KB |
Output is correct |
| 2 |
Correct |
18 ms |
62044 KB |
Output is correct |
| 3 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 4 |
Correct |
17 ms |
62028 KB |
Output is correct |
| 5 |
Correct |
20 ms |
61788 KB |
Output is correct |
| 6 |
Correct |
19 ms |
61788 KB |
Output is correct |
| 7 |
Correct |
17 ms |
61788 KB |
Output is correct |
| 8 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 9 |
Correct |
18 ms |
61788 KB |
Output is correct |
| 10 |
Correct |
18 ms |
62024 KB |
Output is correct |
| 11 |
Execution timed out |
2173 ms |
163840 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
