| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 580986 |
2022-06-22T07:38:07 Z |
박상훈(#8359) |
Robots (APIO13_robots) |
C++17 |
|
126 ms |
57516 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Vertex{
int x, y, d;
Vertex(){}
Vertex(int _x, int _y, int _d): x(_x), y(_y), d(_d) {}
bool operator<(const Vertex &V) const{
return d > V.d;
}
}to[505][505][4];
char a[505][505];
bool visited[505][505][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, w, h;
int dist[81][505][505];
bool chk[81][505][505];
void dfs(int x, int y, int d){
visited[x][y][d] = 1;
int nx, ny, nd = d;
if (a[x][y]=='A') nd = (d+3)%4;
if (a[x][y]=='C') nd = (d+1)%4;
nx = x + dx[nd], ny = y + dy[nd];
if (a[nx][ny]=='x') to[x][y][d] = Vertex(x, y, d);
else if (visited[nx][ny][nd]) to[x][y][d] = to[nx][ny][nd];
else{
dfs(nx, ny, nd);
to[x][y][d] = to[nx][ny][nd];
}
}
void init(){
for (int i=0;i<=h+1;i++) fill(a[i], a[i]+w+2, 'x');
for (int i=1;i<=h;i++){
scanf("%s", a[i]+1);
a[i][w+1] = 'x';
}
for (int i=1;i<=h;i++){
for (int j=1;j<=w;j++){
for (int d=0;d<4;d++) if (!visited[i][j][d]) dfs(i, j, d);
}
}
for (int t=0;t<81;t++){
for (int i=1;i<=h;i++){
for (int j=1;j<=w;j++){
dist[t][i][j] = 1e9;
}
}
}
//printf("%d %d %d\n", to[2][6][1].x, to[2][6][1].y, to[2][6][1].d);
}
void bfs(int t){
int l = t/9, r = t%9;
//printf(" %d %d\n", l, r);
priority_queue<Vertex> pq;
for (int i=1;i<=h;i++){
for (int j=1;j<=w;j++){
if (l==r&& a[i][j]=='1'+l) dist[t][i][j] = 0;
if (dist[t][i][j]<1e9) pq.emplace(i, j, dist[t][i][j]);
}
}
queue<pair<int, int>> q;
while(!pq.empty() || !q.empty()){
if (q.empty()){
while(!pq.empty()){
auto [x, y, d] = pq.top(); pq.pop();
//if (t==21) printf("%d %d %d\n", x, y, d);
if (chk[t][x][y]) continue;
q.emplace(x, y);
break;
}
continue;
}
while(!pq.empty()){
auto [nx, ny] = q.back();
auto [nx2, ny2, d] = pq.top();
assert(d>=dist[t][nx][ny]);
if (d!=dist[t][nx][ny]) break;
if (!chk[t][nx2][ny2]) q.emplace(nx2, ny2);
pq.pop();
}
auto [x, y] = q.front(); q.pop();
//if (t==21 && dist[t][x][y]==2) printf("YES %d %d\n", x, y);
for (int i=0;i<l;i++){
dist[i*9+r][x][y] = min(dist[i*9+r][x][y], dist[i*9+l-1][x][y] + dist[t][x][y]);
}
for (int d=0;d<4;d++){
int nx = to[x][y][d].x, ny = to[x][y][d].y;
//if (!nx) printf("%d %d %d\n", x, y, d);
assert(nx);
//if (t==21 && nx==1 && ny==1) printf(" %d %d\n", dist[t][nx][ny], dist[t][x][y]);
if (dist[t][nx][ny]<=dist[t][x][y]+1) continue;
dist[t][nx][ny] = dist[t][x][y] + 1;
if (dist[t][nx][ny]!=1e9) chk[t][nx][ny] = 1;
q.emplace(nx, ny);
}
}
}
int main(){
scanf("%d %d %d", &n, &w, &h);
init();
for (int d=0;d<n-1;d++){
for (int i=0;i<n-d;i++){
int j = i+d;
bfs(i*9+j);
}
}
int ans = 1e9;
for (int i=1;i<=h;i++){
for (int j=1;j<=w;j++){
//if (dist[0][i][j]==0 && dist[1][i][j]==0) printf("%d %d\n", i, j);
//if (dist[21][i][j]!=1e9)printf("%d ", dist[21][i][j]);
//else printf("x ");
ans = min(ans, dist[n-1][i][j]);
}
//printf("\n");
}
printf("%d\n", ans==1e9?-1:ans);
return 0;
}
Compilation message
robots.cpp: In function 'void init()':
robots.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%s", a[i]+1);
| ~~~~~^~~~~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | scanf("%d %d %d", &n, &w, &h);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
0 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
0 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
0 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 11 |
Correct |
126 ms |
57516 KB |
Output is correct |
| 12 |
Incorrect |
29 ms |
54412 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
0 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2260 KB |
Output is correct |
| 11 |
Correct |
126 ms |
57516 KB |
Output is correct |
| 12 |
Incorrect |
29 ms |
54412 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
