시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 2230 | 547 | 436 | 24.276% |
준규는 오랜만에 회사에 출근하려 한다. 준규는 수학을 엄청 좋아해서 항상 규칙을 정하는데, 강남역에서 내린 준규는 회사까지 가는 길에 깔려있는 보도블록을 보고 규칙을 정하기 시작했다.
위 보도블록 상태를 이용하여 간단한 예시를 들어보자. 1번 규칙으로 밟을 수 있는 블록은 세로 블록이며(색칠 된 블록), 이동 규칙이 오른쪽 이미지와 같다면, 준규는 회사로 가는 여러 경로 중 점선과 실선의 방법으로 출근을 할 수 있다. 실선은 세 걸음으로 출근이 가능한 반면 점선은 두 걸음에 출근이 가능하다.
수학을 좋아하지만 수학을 못하는 준규를 위해서 준규가 만든 규칙으로 출근을 할 수 있는지, 출근이 가능하다면 최소 몇 걸음에 출근이 가능한지 출력하는 프로그램을 작성하시오.
첫 번째 줄에는 보도블록의 세로, 가로 R, C(1 ≤ R, C ≤ 1,000)크기가 주어진다. 다음 R개의 줄에는 C개의 문자로 이루어진 보도블록의 초기 상태가 주어진다. (가로 블록은 0로 표시되고, 세로 블록은 1로 표시된다.) 그 다음 줄에 이동 가능한 규칙의 개수 N(0 ≤ N ≤ 10)이 주어지고 그 다음 N개의 줄에 걸쳐 규칙 r(-R ≤ r ≤ R), c(-C ≤ c ≤ C)가 주어진다. 이 뜻은 현재 위치가 (0, 0) 일 때 (0+r, 0+c)로 이동 할 수 있음을 의미한다. ((0,0)왼쪽 위, (R – 1, C – 1)오른쪽 아래 블록이다.)
준규가 출근을 하는데 최소 몇 번의 걸음을 걸어야 하는지 출력한다. 만약 출근할 수 없다면 -1을 출력한다.
4 5 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 8 -2 -1 -2 1 -1 -2 -1 2 1 -2 1 2 2 -1 2 1
2