| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15939 |
2015-08-02T09:01:09 Z |
myungwoo |
Robots (APIO13_robots) |
C++14 |
|
931 ms |
112896 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mt make_tuple
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
int yy[]={-1, 0, 1, 0}, xx[]={0, 1, 0, -1};
int R, N, M;
int D[10][10][501][501];
int Y[501][501][4], X[501][501][4];
bool needless[501][501][4], V[501][501][4];
char A[501][502];
bool dfs(int y, int x, int d)
{
if (V[y][x][d]){
if (!Y[y][x][d]) needless[y][x][d] = 1;
return needless[y][x][d];
}
V[y][x][d] = 1;
int nd = d;
if (A[y][x] == 'A') nd = (d+3)%4;
if (A[y][x] == 'C') nd = (d+1)%4;
int ny = y+yy[nd], nx = x+xx[nd];
if (ny < 1 || nx < 1 || ny > N || nx > M || A[ny][nx] == 'x'){
Y[y][x][d] = y; X[y][x][d] = x;
return 0;
}
dfs(ny, nx, nd);
if (needless[ny][nx][nd]) needless[y][x][d] = 1;
Y[y][x][d] = Y[ny][nx][nd], X[y][x][d] = X[ny][nx][nd];
return needless[y][x][d];
}
void bfs(int dst[501][501])
{
vector <tuple<int, int, int>> arr;
for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) if (dst[i][j] < 1e9){
arr.pb(mt(dst[i][j], i, j));
}
if (arr.empty()) return;
sort(all(arr));
int pnt = 1;
queue <int> que;
que.push(get<1>(arr[0])); que.push(get<2>(arr[0]));
while (!que.empty()){
int y = que.front(); que.pop();
int x = que.front(); que.pop();
while (pnt < sz(arr) && dst[y][x]+1 >= get<0>(arr[pnt])){
int ty = get<1>(arr[pnt]), tx = get<2>(arr[pnt]);
if (dst[ty][tx] == get<0>(arr[pnt]))
que.push(ty), que.push(tx);
pnt++;
}
for (int d=0;d<4;d++){
if (dfs(y, x, d)) continue;
int ny = Y[y][x][d], nx = X[y][x][d];
if (dst[ny][nx] > dst[y][x]+1)
dst[ny][nx] = dst[y][x]+1, que.push(ny), que.push(nx);
}
}
}
int main()
{
scanf("%d%d%d", &R, &M, &N);
for (int i=1;i<=N;i++) scanf("%s", A[i]+1);
for (int i=1;i<=R;i++){
for (int j=1;j<=N;j++) for (int k=1;k<=M;k++){
D[i][i][j][k] = (A[j][k]-'0' == i) ? 0 : 1e9;
}
bfs(D[i][i]);
}
for (int l=2;l<=R;l++){
for (int s=1;s<=R-l+1;s++){
int e = s+l-1;
for (int y=1;y<=N;y++) for (int x=1;x<=M;x++){
D[s][e][y][x] = 1e9;
for (int k=s;k<e;k++){
D[s][e][y][x] = min(D[s][e][y][x], D[s][k][y][x] + D[k+1][e][y][x]);
}
}
bfs(D[s][e]);
}
}
int ans = 1e9;
for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
ans = min(ans, D[1][R][i][j]);
}
printf("%d\n", ans < 1e9 ? ans : -1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 2 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 3 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 4 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 5 |
Correct |
0 ms |
109828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 2 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 3 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 4 |
Correct |
0 ms |
109828 KB |
Output is correct |
| 5 |
Correct |
0 ms |
109828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
110592 KB |
Output is correct |
| 2 |
Correct |
7 ms |
109828 KB |
Output is correct |
| 3 |
Correct |
27 ms |
109828 KB |
Output is correct |
| 4 |
Correct |
323 ms |
111360 KB |
Output is correct |
| 5 |
Correct |
85 ms |
110212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
109828 KB |
Output is correct |
| 2 |
Correct |
931 ms |
112896 KB |
Output is correct |
| 3 |
Correct |
224 ms |
111360 KB |
Output is correct |
| 4 |
Correct |
160 ms |
109828 KB |
Output is correct |
| 5 |
Correct |
642 ms |
112896 KB |
Output is correct |
