| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 580889 |
2022-06-22T05:21:55 Z |
반딧불(#8360) |
로봇 (APIO13_robots) |
C++17 |
|
1500 ms |
59396 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int xx[]={0, -1, 0, 1}, yy[]={1, 0, -1, 0};
int n, m, k;
char board[502][502];
int sx[10], sy[10];
void input();
void operate();
void output();
int main(){
input();
operate();
output();
}
void input(){
scanf("%d %d %d", &k, &m, &n);
for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) board[i][j] = 'x';
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
scanf(" %c", &board[i][j]);
if(isdigit(board[i][j])){
int tmp = board[i][j] - '0';
sx[tmp] = i, sy[tmp] = j;
board[i][j] = '.';
}
}
}
int endpointX[502][502][4];
int endpointY[502][502][4];
void calculateEndpoints(){
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) for(int d=0; d<4; d++) endpointX[i][j][d] = -1;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(board[i][j]=='x') continue;
for(int d=0; d<4; d++){
if(board[i+xx[d]][j+yy[d]]!='x') continue;
int x=i, y=j, td=d;
while(board[x][y]!='x'){
if(board[x][y]=='A') td=(td+3)%4;
if(board[x][y]=='C') td=(td+1)%4;
endpointX[x][y][td] = i;
endpointY[x][y][td] = j;
x-=xx[td], y-=yy[td];
}
}
}
}
}
int DP[10][10][502][502];
void init(){
for(int l=1; l<=k; l++) for(int r=l; r<=k; r++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
DP[l][r][i][j] = 1e9;
}
for(int i=1; i<=k; i++){
DP[i][i][sx[i]][sy[i]] = 0;
}
}
struct dat{
int x, y, d;
dat(){}
dat(int x, int y, int d): x(x), y(y), d(d){}
bool operator<(const dat &r)const{
return d>r.d;
}
};
bool visited[502][502];
void calculateDP(int l, int r){
memset(visited, 0, sizeof(visited));
priority_queue<dat> pq;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
pq.push(dat(i, j, DP[l][r][i][j]));
}
}
while(!pq.empty()){
dat tmp = pq.top();
pq.pop();
int x = tmp.x, y = tmp.y, d = tmp.d;
// printf("%d %d %d\n", x, y, d);
if(d>=1e9 || visited[x][y]) continue;
DP[l][r][x][y] = d;
visited[x][y] = 1;
for(int c=0; c<4; c++){
if(endpointX[x][y][c] == -1) continue;
if(visited[endpointX[x][y][c]][endpointY[x][y][c]]) continue;
pq.push(dat(endpointX[x][y][c], endpointY[x][y][c], d+1));
}
}
}
void operate(){
calculateEndpoints();
init();
for(int d=0; d<k; d++){
for(int i=1; i+d<=k; i++){
int j = i+d;
for(int mid=i; mid<j; mid++){
for(int x=1; x<=n; x++){
for(int y=1; y<=m; y++){
DP[i][j][x][y] = min(DP[i][j][x][y], DP[i][mid][x][y] + DP[mid+1][j][x][y]);
}
}
}
calculateDP(i, j);
}
}
#ifdef TEST
for(int i=1; i<=k; i++) for(int j=i; j<=k; j++){
printf("Matrix %d %d:\n", i, j);
for(int x=1; x<=n; x++){
for(int y=1; y<=m; y++){
printf("%3d ", DP[i][j][x][y]>100?100:DP[i][j][x][y]);
}
puts("");
}
}
#endif
}
void output(){
int ans = INT_MAX;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ans = min(ans, DP[1][k][i][j]);
if(ans >= 1e9) printf("-1");
else printf("%d", ans);
}
Compilation message
robots.cpp: In function 'void input()':
robots.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | scanf("%d %d %d", &k, &m, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf(" %c", &board[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Correct |
1 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Correct |
1 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Correct |
578 ms |
34440 KB |
Output is correct |
| 12 |
Correct |
20 ms |
7500 KB |
Output is correct |
| 13 |
Correct |
323 ms |
24776 KB |
Output is correct |
| 14 |
Correct |
754 ms |
34584 KB |
Output is correct |
| 15 |
Correct |
571 ms |
34496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
596 KB |
Output is correct |
| 9 |
Correct |
1 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Correct |
578 ms |
34440 KB |
Output is correct |
| 12 |
Correct |
20 ms |
7500 KB |
Output is correct |
| 13 |
Correct |
323 ms |
24776 KB |
Output is correct |
| 14 |
Correct |
754 ms |
34584 KB |
Output is correct |
| 15 |
Correct |
571 ms |
34496 KB |
Output is correct |
| 16 |
Correct |
1485 ms |
59396 KB |
Output is correct |
| 17 |
Execution timed out |
1576 ms |
59124 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
