| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258567 |
2020-08-06T07:09:28 Z |
pure_mem |
Robots (APIO13_robots) |
C++14 |
|
87 ms |
163844 KB |
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int inf = 250000, N = 500;
char a[N][N];
int n, w, h, dp[9][9][N][N];
pair<int, int> end_pos[4][N][N];
queue< pair<int, int> > q[inf];
queue< pair< int, pair< int, int > > > temp;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(dp, 0x3f, sizeof(dp));
cin >> n >> w >> h;
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
cin >> a[i][j];
if(a[i][j] >= '0' && a[i][j] <= '9'){
dp[a[i][j] - '0' - 1][a[i][j] - '0' - 1][i][j] = 0;
}
}
}
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] == 'x')
continue;
for(int d = 0;d < 4;d++){
int dr = d;
if(a[x][y] == 'A')
dr = (dr + 3) % 4;
else if(a[x][y] == 'C')
dr = (dr + 1) % 4;
pair<int, int> pos = MP(x, y);
while(true){
if(dr == 0){
if(pos.X - 1 >= 0 && pos.X - 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X - 1][pos.Y] != 'x')
pos.X -= 1;
else
break;
}
else if(dr == 3){
if(pos.X >= 0 && pos.X < h && pos.Y - 1 >= 0 && pos.Y - 1 < w && a[pos.X][pos.Y - 1] != 'x')
pos.Y -= 1;
else
break;
}
else if(dr == 2){
if(pos.X + 1 >= 0 && pos.X + 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X + 1][pos.Y] != 'x')
pos.X += 1;
else
break;
}
else if(dr == 1){
if(pos.X >= 0 && pos.X < h && pos.Y + 1 >= 0 && pos.Y + 1 < w && a[pos.X][pos.Y + 1] != 'x')
pos.Y += 1;
else
break;
}
if(end_pos[dr][pos.X][pos.Y] != MP(0, 0)){
pos = end_pos[dr][pos.X][pos.Y];
break;
}
else{
temp.push(MP(dr, pos));
}
if(a[pos.X][pos.Y] == 'A')
dr = (dr + 3) % 4;
else if(a[pos.X][pos.Y] == 'C')
dr = (dr + 1) % 4;
}
end_pos[d][x][y] = pos;
while(!temp.empty()){
end_pos[temp.front().X][temp.front().Y.X][temp.front().Y.Y] = pos;
temp.pop();
}
}
}
}
int ans = inf;
for(int len = 1;len < n;len++){
for(int A = 0;A + len - 1 < n;A++){
int B = A + len - 1;
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] != 'x' && dp[A][B][x][y] < inf){
q[dp[A][B][x][y]].push(MP(x, y));
}
}
}
for(int it = 0;it < inf;it++){
while(!q[it].empty()){
pair<int, int> pos = q[it].front();
q[it].pop();
for(int dr = 0;dr < 4;dr++){
pair<int, int> to = end_pos[dr][pos.X][pos.Y];
if(dp[A][B][pos.X][pos.Y] + 1 < dp[A][B][to.X][to.Y]){
dp[A][B][to.X][to.Y] = dp[A][B][pos.X][pos.Y] + 1;
if(it + 1 < inf)
q[it + 1].push(to);
}
}
}
}
}
for(int A = 0;A + len < n;A++){
int B = A + len;
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] != 'x'){
for(int C = A;C < B;C++){
dp[A][B][x][y] = min(dp[A][B][x][y], dp[A][C][x][y] + dp[C + 1][B][x][y]);
}
}
}
}
}
}
/*
cerr << end_pos[0][3][0].X << " " << end_pos[0][3][0].Y << "\n";
cerr << dp[1][1][1][0] << "\n"; */
for(int x = 0;x < h;x++){
for(int y = 0;y < w;y++){
if(a[x][y] != 'x')
ans = min(ans, dp[0][n - 1][x][y]);
}
}
if(ans >= inf)
ans = -1;
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
