| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 122322 |
2019-06-28T04:57:05 Z |
이온조(#2989) |
로봇 (APIO13_robots) |
C++14 |
|
142 ms |
59104 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct node {
int x, y, s, e;
};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
char A[509][509];
int D[501][501][10][10];
bool vs[501][501][10][10];
vector<node> S[1000009];
pii go(int x, int y, int dir) {
while(1) {
// printf("in go: x: %d, y: %d, dir: %d\n", x, y, dir);
if(A[x][y] == 'A') dir += 3, dir %= 4;
if(A[x][y] == 'C') dir += 1, dir %= 4;
int X = x + dx[dir], Y = y + dy[dir];
if(A[X][Y] == 'x') break;
x = X; y = Y;
}
// puts("done");
return {x, y};
}
inline void mark(node X, int dist) {
int a = X.x, b = X.y, c = X.s, d = X.e;
vs[a][b][c][d] = 1; D[a][b][c][d] = dist;
}
int main() {
int N, W, H; scanf("%d%d%d",&N,&W,&H);
for(int i=0; i<=H+1; i++) for(int j=0; j<=W+1; j++) A[i][j] = 'x';
for(int i=1; i<=H; i++) {
for(int j=1; j<=W; j++) {
scanf(" %c", &A[i][j]);
if('1' <= A[i][j] && A[i][j] <= '9') {
int id = A[i][j] - '0';
S[0].push_back({i, j, id, id});
}
}
}
int sum = 0, fmn;
for(int i=1; i<=N; i++) {
queue<node> que;
int c = 0;
do {
for(auto& it: S[c]) if(!vs[it.x][it.y][it.s][it.e] && it.e - it.s + 1 == i) {
que.push(it);
mark(it, sum + c);
}
S[c].clear();
int sz = que.size();
while(sz--) {
node P = que.front(); que.pop();
// printf("i: %d, dist: %d, x: %d, y: %d, s: %d, e: %d\n", i, sum + c, P.x, P.y, P.s, P.e);
for(int k=0; k<4; k++) {
int X, Y; tie(X, Y) = go(P.x, P.y, k);
// printf("X: %d, Y: %d\n", X, Y);
if(!vs[X][Y][P.s][P.e]) {
que.push({X, Y, P.s, P.e});
mark({X, Y, P.s, P.e}, sum + c + 1);
}
}
}
++c;
} while(que.size());
if(i == N) break;
// puts("CALCULATE START");
int gmn = 1e9;
vector<pair<int, node> > R;
for(int p=1; p<=H; p++) {
for(int q=1; q<=W; q++) {
for(int j=i+1; j<=N; j++) {
int l = j - i, r = j, mn = 1e9;
for(int k=l; k<r; k++) {
// printf("p: %d, q: %d, l: %d, r: %d, k: %d\n", p, q, l, r, k);
if(vs[p][q][l][k] && vs[p][q][k+1][r]) {
// printf("value: %d\n", D[p][q][l][k] + D[p][q][k+1][r]);
gmn = min(gmn, D[p][q][l][k] + D[p][q][k+1][r]);
mn = min(mn, D[p][q][l][k] + D[p][q][k+1][r]);
}
}
if(mn != 1e9) R.push_back({mn, {p, q, l, r}});
}
}
}
for(auto& it: R) {
// printf("value: %d gmn: %d\n", it.first, gmn);
if(it.first - gmn < fmn) S[it.first - gmn].push_back(it.second);
}
sum = gmn;
if(sum == 1e9) break;
if(i == 1) fmn = c * 2;
}
if(sum == 1e9) puts("-1");
else printf("%d", sum);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:36:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N, W, H; scanf("%d%d%d",&N,&W,&H);
~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:40:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &A[i][j]);
~~~~~^~~~~~~~~~~~~~~~~
robots.cpp:95:4: warning: 'fmn' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(it.first - gmn < fmn) S[it.first - gmn].push_back(it.second);
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23960 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 7 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 9 |
Correct |
25 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
24 ms |
23928 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23960 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 7 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 9 |
Correct |
25 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 11 |
Incorrect |
142 ms |
59104 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
24 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
22 ms |
23960 KB |
Output is correct |
| 6 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 7 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
23 ms |
23808 KB |
Output is correct |
| 9 |
Correct |
25 ms |
23808 KB |
Output is correct |
| 10 |
Correct |
24 ms |
23928 KB |
Output is correct |
| 11 |
Incorrect |
142 ms |
59104 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
