만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

세 번 이내에 사과를 먹자

면접 대비

시간 제한1초메모리 제한512 MB

요약
5 x 5 격자에서 학생이 주어진 칸에서 출발해 3번 이내로 움직여 사과를 2개 이상 먹을 수 있는지 판단합니다.
난이도

보통10점 중 4점

유형
백트래킹, 완전 탐색, 행렬
정답자
아직 제출이 없습니다

문제

5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 각 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸 중 하나다.

격자의 위치는 (r,c)(r, c)로 나타낸다. rr은 행 번호, cc는 열 번호다. 행 번호는 맨 위가 0이고 아래 방향으로 1씩 커진다. 열 번호는 맨 왼쪽이 0이고 오른쪽으로 1씩 커진다. 따라서 맨 왼쪽 위 격자는 (0,0)(0, 0), 맨 아래 오른쪽 격자는 (4,4)(4, 4)다.

한 학생이 (r,c)(r, c) 위치에 있다. 학생은 한 번에 상, 하, 좌, 우 중 한 방향으로 한 칸 이동할 수 있다. 사과가 있는 격자로 이동하면 그 격자의 사과를 1개 먹는다. 장애물이 있는 격자로는 이동할 수 없다. 학생이 지나간 격자는 학생이 그 격자를 떠나는 즉시 장애물이 있는 격자로 바뀐다. 즉, 학생이 그 격자에서 상, 하, 좌, 우로 한 칸 움직이면 그 격자는 바로 장애물이 된다.

학생이 현재 위치 (r,c)(r, c)에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을, 그렇지 않으면 0을 출력한다.

입력

첫 번째 줄부터 다섯 번째 줄까지 보드의 정보가 주어진다. ii번째 줄의 jj번째 수는 보드의 (i−1)(i-1)번째 행, (j−1)(j-1)번째 열의 정보를 나타낸다. 값이 1이면 사과가 1개 있는 격자, 0이면 빈칸, -1이면 장애물이 있는 격자다.

다음 줄에는 학생의 현재 위치 rr, cc가 빈칸을 사이에 두고 차례로 주어진다.

출력

첫 번째 줄에 학생이 현재 위치 (r,c)(r, c)에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을, 먹을 수 없으면 0을 출력한다.

제한

0≤r,c≤40 \le r, c \le 4

현재 위치 (r,c)(r, c)는 빈칸이다.

예제2

  1. 예제 1

    입력
    0 0 1 0 0
    0 0 -1 0 0
    0 0 1 0 0
    1 1 -1 1 0
    0 0 0 -1 0
    4 1
    
    예상 출력
    1
    
  2. 예제 2

    입력
    0 0 1 0 0
    0 0 -1 0 0
    0 0 1 0 0
    1 0 -1 1 0
    0 0 0 -1 0
    2 3
    
    예상 출력
    0