oj.uz

Submission #122381

# Submission time Handle Problem Language Result Execution time Memory
122381 2019-06-28T06:35:47 Z 송준혁(#2992) Robots (APIO13_robots) C++14
30 / 100
 7 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int N, M;
bool chk[11][11][11][11];
char A[20][20];

struct Data{
    int ax, ay, bx, by, d;
};
queue<Data> Q;

int main(){
    int ax, ay, bx, by;
    scanf("%*d %d %d", &M, &N);
    memset(A, 'x', sizeof A);
    for (int i=1; i<=N; i++) for (int j=1; j<=M; j++){
        scanf(" %c", &A[i][j]);
        if (A[i][j] == '1') ax=i, ay=j, A[i][j] = '.';
        if (A[i][j] == '2') bx=i, by=j, A[i][j] = '.';
    }
    Q.push((Data){ax, ay, bx, by, 0});
    chk[ax][ay][bx][by] = true;

    while (!Q.empty()){
        Data T = Q.front();
        Q.pop();
        if (T.ax == T.bx && T.ay == T.by){
            printf("%d\n", T.d);
            return 0;
        }
        for (int i=0; i<4; i++){
            int t = i, x = T.ax, y = T.ay;
            while (1){
                if (A[x][y] == 'A') t = (t+3)%4;
                if (A[x][y] == 'C') t = (t+1)%4;
                if (A[x+dx[t]][y+dy[t]] == 'x') break;
                x += dx[t];
                y += dy[t];
            }
            if (chk[x][y][T.bx][T.by]) continue;
            Q.push((Data){x, y, T.bx, T.by, T.d+1});
            chk[x][y][T.bx][T.by] = true;
        }
        for (int i=0; i<4; i++){
            int t = i, x = T.bx, y = T.by;
            while (1){
                if (A[x][y] == 'A') t = (t+3)%4;
                if (A[x][y] == 'C') t = (t+1)%4;
                if (A[x+dx[t]][y+dy[t]] == 'x') break;
                x += dx[t];
                y += dy[t];
            }
            if (chk[T.ax][T.ay][x][y]) continue;
            Q.push((Data){T.ax, T.ay, x, y, T.d+1});
            chk[T.ax][T.ay][x][y] = true;
        }
    }
    printf("-1\n");
    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*d %d %d", &M, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
robots.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &A[i][j]);
         ~~~~~^~~~~~~~~~~~~~~~~
robots.cpp:26:25: warning: 'by' may be used uninitialized in this function [-Wmaybe-uninitialized]
     chk[ax][ay][bx][by] = true;
     ~~~~~~~~~~~~~~~~~~~~^~~~~~
robots.cpp:26:25: warning: 'bx' may be used uninitialized in this function [-Wmaybe-uninitialized]
robots.cpp:26:25: warning: 'ay' may be used uninitialized in this function [-Wmaybe-uninitialized]
robots.cpp:26:25: warning: 'ax' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 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 0 ms 128 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 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 0 ms 128 KB Output is correct
11 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 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 0 ms 128 KB Output is correct
11 Runtime error 7 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -