시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1482 | 214 | 148 | 21.264% |
김주성은 사실 뛰어난 발레 실력을 숨기고 있다. 그는 매일 밤 열심히 발레 연습을 한다.
그는 항상 연습하는 곳의 바닥을 m행 n열의 정사각형 칸들로 나누어 놓고 춤을 춘다. 그가 춤을 추는 방식은 이 직사각형 격자판 위를 점프하여 돌아다니는 것인데, 현재 위치하고 있는 칸에서 점프할 수 있는 위치는 체스판 위의 나이트 (knight)가 이동할 수 있는 곳과 같다. (나이트의 이동 규칙을 모르는 경우 검색해 볼 것. ㅜ.ㅜ) 김주성은 특정한 위치에서 춤을 시작하여, 특정한 위치에서 춤을 마치고 싶다.
밤중에 쿵쿵거리면 실례이므로, 바닥에 방석을 깔아 놓고 춤을 추려고 한다. 방석은 격자칸 한 칸에 꼭 맞는 크기이고, 몇 개의 칸에는 방석이 이미 놓여 있다. 특히, 김 조교가 현재 서 있는 위치와, 최종적으로 도달하려고 하는 위치에는 이미 방석이 놓여 있다.
여러분이 할 일은 최소한의 방석을 더 놓아서 김주성의 춤이 가능하도록 만들고, 그렇게 할 수 있는 방법이 모두 몇 가지인지 계산하는 것이다. 다만, 돌멩이가 놓여 있는 칸도 있는데, 그 부분에는 방석을 놓지 않는다. 부상의 위험이 있기 때문이다.
첫째 줄에 m과 n이 주어진다. (1 ≤ m, n ≤ 30)
이어지는 m개의 줄에는 각 행의 정보를 제공하는 n개의 숫자가 주어진다. 0은 맨땅, 1은 방석이 깔린 곳 중 김주성이 춤을 시작하거나 마치지 않는 위치, 2는 돌멩이가 있는 위치, 3은 김주성이 춤을 시작하는 위치 (방석이 깔려 있음), 4는 김주성이 춤을 마치는 위치 (방석이 깔려 있음)이다.
첫 줄에 필요한 최소의 방석 수를 출력한다. 만약 아무리 방석을 많이 놓아도 김주성의 춤이 불가능할 경우엔, -1을 출력한다. 둘째 줄엔 방석을 놓는 방법의 수를 출력한다. (이 수는 64-bit signed integer 범위 내에 있음을 보장한다.) 만약 첫 줄에 -1을 출력한 경우에는, 둘째 줄은 출력하지 않는다.
4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0
2 3
4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0
입출력 예시의 세 가지 경우는 다음과 같다. X표 친 곳에 방석을 놓으면 된다.
1 0 0 0 0 1 0 X 0 0 1 0 X 0 0 3 0 X 0 0 3 0 0 0 0 3 0 0 0 X 0 0 2 0 0 0 X 2 0 0 0 0 2 0 0 0 X 0 4 0 0 0 0 4 0 0 0 0 4 0