| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 580891 |
2022-06-22T05:26:58 Z |
반딧불(#8360) |
Robots (APIO13_robots) |
C++17 |
|
84 ms |
32508 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));
vector<dat> vec;
queue<dat> que;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(DP[l][r][i][j] >= 1e9) continue;
vec.push_back(dat(i, j, DP[l][r][i][j]));
}
}
sort(vec.begin(), vec.end());
int pnt = 0;
while(!que.empty() || pnt < (int)vec.size()){
if(que.empty()){
que.push(vec[pnt++]);
}
dat tmp;
if(pnt < (int)vec.size() && vec[pnt].d <= que.front().d) tmp = vec[pnt++];
else tmp = que.front(), que.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;
que.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]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Incorrect |
84 ms |
32508 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
596 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Incorrect |
84 ms |
32508 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
