oj.uz

Submission #580967

# Submission time Handle Problem Language Result Execution time Memory
580967 2022-06-22T07:06:18 Z 조영욱(#8362) Robots (APIO13_robots) C++17
30 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

int n,w,h;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1}; //�ݽð� : +1 �ð� : -1
int arr[10][10]; //0 : �� 1 : �׳� 2 : �ݽð� 3 :�ð�
int dist[100][100];
const int INF=1e6;

bool valid(int x,int y) {
    return arr[x][y]!=0&&x>=0&&x<h&&y>=0&&y<w;
}

int main(void) {
    scanf("%d %d %d\n",&n,&w,&h);
    int x1,y1,x2,y2;
    for(int i=0;i<h;i++) {
        for(int j=0;j<w;j++) {
            char c;
            scanf("%c",&c);
            if (c=='1') {
                x1=i;
                y1=j;
                arr[i][j]=1;
            }
            else if (c=='2') {
                x2=i;
                y2=j;
                arr[i][j]=1;
            }
            else if (c=='x') {
                arr[i][j]=0;
            }
            else if (c=='A') {
                arr[i][j]=2;
            }
            else if (c=='C') {
                arr[i][j]=3;
            }
            else {
                arr[i][j]=1;
            }
        }
        scanf("\n");
    }
    for(int i=0;i<h*w;i++) {
        for(int j=0;j<h*w;j++) {
            dist[i][j]=(i==j?0:INF);
        }
    }
    for(int x=0;x<h;x++) {
        for(int y=0;y<w;y++) {
            if (!valid(x,y)) {
                continue;
            }
            for(int d=0;d<4;d++) {
                bool flag=true;
                int nx=x;
                int ny=y;
                int nd=d;
                bool temp[10][10];
                memset(temp,0,sizeof(temp));
                while (1) {
                    if (temp[nx][ny]) {
                        flag=false;
            break;
                    }
                    temp[nx][ny]=true;
                    if (arr[nx][ny]==2) {
                        nd=(nd+1)%4;
                    }
                    if (arr[nx][ny]==3) {
                        nd=(nd+3)%4;
                    }
                    if (!valid(nx+dx[nd],ny+dy[nd])) {
                        break;
                    }
                    nx+=dx[nd];
                    ny+=dy[nd];
                }
                if (flag) {
                    if (x*w+y!=nx*w+ny)
                    dist[x*w+y][nx*w+ny]=1;
                    //printf("%d %d %d %d %d\n",x,y,d,nx,ny);
                }
            }
        }
    }
    for(int k=0;k<h*w;k++) {
        for(int i=0;i<h*w;i++) {
            for(int j=0;j<h*w;j++) {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    int ret=INF;
    for(int i=0;i<h*w;i++) {
        if (arr[i/w][i%w]!=0) {
            ret=min(ret,dist[x1*w+y1][i]+dist[x2*w+y2][i]);
        }
    }
    printf("%d",ret==INF?-1:ret);
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d %d\n",&n,&w,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |             scanf("%c",&c);
      |             ~~~~~^~~~~~~~~
robots.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("\n");
      |         ~~~~~^~~~~~
robots.cpp:17:18: warning: 'y2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     int x1,y1,x2,y2;
      |                  ^~
robots.cpp:17:15: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     int x1,y1,x2,y2;
      |               ^~
robots.cpp:17:12: warning: 'y1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     int x1,y1,x2,y2;
      |            ^~
robots.cpp:17:9: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     int x1,y1,x2,y2;
      |         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Runtime error 1 ms 340 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Runtime error 1 ms 340 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -