| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122394 |
2019-06-28T06:58:04 Z |
임유진(#2991) |
Robots (APIO13_robots) |
C++14 |
|
3 ms |
384 KB |
#include<stdio.h>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
int movement[4][2]={{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
char m[12][12];
int rot[12][12];
int moveto[12][12][4];
int dp[144][144];
int main(){
int N, W, H;
int y[2], x[2];
int ans=10001;
scanf("%d%d%d", &N, &W, &H);
for(int i=1; i<=H; i++) scanf("%s", m[i]+1);
for(int i=0; i<=H+1; i++) m[i][0]=m[i][W+1]='x';
for(int i=1; i<=W; i++) m[0][i]=m[H+1][i]='x';
for(int i=1; i<=H; i++) for(int j=1; j<=W; j++){
if(m[i][j]=='C') rot[i][j]=-1;
else if(m[i][j]=='A') rot[i][j]=1;
else rot[i][j]=0;
if(m[i][j]=='1'){
y[0]=i;
x[0]=j;
}
else if(m[i][j]=='2'){
y[1]=i;
x[1]=j;
}
}
/*
for(int i=1; i<=H; i++){
for(int j=1; j<=W; j++) printf("%d ", rot[i][j]);
printf("\n");
}
*/
queue<pii> q;
for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) if(m[i][j]!='x'){
for(int k=0; k<4; k++){
int kk=(k+rot[i][j]+4)%4;
if(m[i+movement[kk][0]][j+movement[kk][1]]=='x'){
//printf("i=%d, j=%d, k=%d\n", i, j, k);
moveto[i][j][k]=i*12+j;
q.push(make_pair(i*12+j, k));
}
else moveto[i][j][k]=-1;
}
}
/*
printf("%d\n", q.size());
for(int i=1; i<=H; i++){
for(int j=1; j<=W; j++){
printf("[");
for(int k=0; k<4; k++){
if(moveto[i][j][k]!=-1) printf("(%d, %d)", moveto[i][j][k]/12, moveto[i][j][k]%12);
else printf("-");
}
printf("]");
}
printf("\n");
}
*/
while(!q.empty()){
pii t=q.front();
q.pop();
int k=t.second;
int i=t.first/12-movement[k][0], j=t.first%12-movement[k][1];
if(0<i&&i<=H&&0<j&&j<=W&&m[i][j]!='x'){
int kk=(k-rot[i][j]+4)%4;
//printf("i=%d, j=%d, k=%d, kk=%d\n", i, j, k, kk);
if(moveto[i][j][kk]==-1){
moveto[i][j][kk]=moveto[i+movement[k][0]][j+movement[k][1]][k];
//if(i==2&&j==1) printf("t=(%d, %d)\n", t.first, t.second);
q.push(make_pair(i*12+j, kk));
}
}
}
/*
for(int i=1; i<=H; i++){
for(int j=1; j<=W; j++){
printf("[");
for(int k=0; k<4; k++){
if(moveto[i][j][k]!=-1) printf("(%d, %d)", moveto[i][j][k]/12, moveto[i][j][k]%12);
else printf("-");
}
printf("]");
}
printf("\n");
}
*/
for(int i=1; i<144; i++) for(int j=1; j<144; j++) dp[i][j]=-1;
q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
dp[ y[0]*12+x[0] ][ y[1]*12+x[1] ] = 0;
while(!q.empty()){
pii t=q.front();
q.pop();
//if(t.first==t.second) printf("[(%d, %d), (%d, %d)]\n", t.first / 12, t.first % 12, t.second/12, t.second%12);
if(t.first==t.second){
int i=t.first/12, j=t.first%12;
for(int k=0; k<4; k++){
int mt = moveto[i][j][k];
if( dp[mt][mt] == -1 ) {
dp[mt][mt] = dp[t.first][t.second] + 1;
q.push(make_pair(mt, mt));
}
}
}
else {
int i=t.first/12, j=t.first%12;
for(int k=0; k<4; k++){
int mt = moveto[i][j][k];
if( dp[mt][t.second] == -1 ) {
dp[mt][t.second] = dp[t.first][t.second] + 1;
q.push( make_pair( mt, t.second) );
}
}
i = t.second/12, j = t.second%12;
for(int k=0; k<4; k++){
int mt = moveto[i][j][k];
if( dp[t.first][mt] == -1){
dp[t.first][mt] = dp[t.first][t.second]+1;
q.push( make_pair( t.first, mt) );
}
}
}
}
for(int i=1; i<=H; i++) for(int j=1; j<=W; j++){
int t=i*12+j;
if( dp[t][t] != -1) ans = min(ans, dp[t][t]);
}
printf("%d", ans==10001?-1:ans);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &W, &H);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=H; i++) scanf("%s", m[i]+1);
~~~~~^~~~~~~~~~~~~~
robots.cpp:101:23: warning: 'y[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
~~~~^~~
robots.cpp:101:40: warning: 'x[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
~~~~~~~^~~~~
robots.cpp:101:26: warning: 'x[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
~~~~~~~^~~~~
robots.cpp:101:37: warning: 'y[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
3 ms |
384 KB |
Time limit exceeded (wall clock) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
3 ms |
384 KB |
Time limit exceeded (wall clock) |
| 12 |
Halted |
0 ms |
0 KB |
- |
