세 번 이내에 사과를 먹자
면접 대비시간 제한1초메모리 제한512 MB
5 x 5 격자에서 학생이 주어진 칸에서 출발해 3번 이내로 움직여 사과를 2개 이상 먹을 수 있는지 판단합니다.
문제
5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 각 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸 중 하나다.
격자의 위치는 로 나타낸다. 은 행 번호, 는 열 번호다. 행 번호는 맨 위가 0이고 아래 방향으로 1씩 커진다. 열 번호는 맨 왼쪽이 0이고 오른쪽으로 1씩 커진다. 따라서 맨 왼쪽 위 격자는 , 맨 아래 오른쪽 격자는 다.
한 학생이 위치에 있다. 학생은 한 번에 상, 하, 좌, 우 중 한 방향으로 한 칸 이동할 수 있다. 사과가 있는 격자로 이동하면 그 격자의 사과를 1개 먹는다. 장애물이 있는 격자로는 이동할 수 없다. 학생이 지나간 격자는 학생이 그 격자를 떠나는 즉시 장애물이 있는 격자로 바뀐다. 즉, 학생이 그 격자에서 상, 하, 좌, 우로 한 칸 움직이면 그 격자는 바로 장애물이 된다.
학생이 현재 위치 에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을, 그렇지 않으면 0을 출력한다.
입력
첫 번째 줄부터 다섯 번째 줄까지 보드의 정보가 주어진다. 번째 줄의 번째 수는 보드의 번째 행, 번째 열의 정보를 나타낸다. 값이 1이면 사과가 1개 있는 격자, 0이면 빈칸, -1이면 장애물이 있는 격자다.
다음 줄에는 학생의 현재 위치 , 가 빈칸을 사이에 두고 차례로 주어진다.
출력
첫 번째 줄에 학생이 현재 위치 에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을, 먹을 수 없으면 0을 출력한다.
제한
현재 위치 는 빈칸이다.