#2715 가 시

1 s   128 MB  

Description

가로가 C 세로가 R인 직사각형 모양의 밭이 있다.

이 공간에는 곳곳에 바위와 땅굴이 존재한다.

이곳엔  고슴도치와 두더지가 한마리씩 산다.

고슴도치는 가시 없이 민둥거리는 몸이 섹시한 두더지를 너무 좋아 한다.

점점 빠져 살더니 급기야는 움직이는 방향으로 똑같이 움직인다.

(단, 두더지가 움직이지 못하는 방향인데, 고슴도치가 움직일 수 있다면, 고슴도치만 움직인다.

마찬가지로, 고슴도치가 움직이지 못하는 방향인데, 두더지가 움직일 수 있다면, 두더지만 움직인다.)

하지만 곳곳엔 바위와 땅굴이 존재하기 때문에 조심해야 한다.

이동하려는 방향에 바위가 있으면 고슴도치와 두더지 모두 그 곳엔 가지 못한다.

하지만 땅굴이 있으면 두더지는 갈 수 있고 고슴도치는 갈 수 없다.

두더지는 자꾸 따라다니는 고슴도치가 지겨워서 얼른 땅굴로 사라지고 싶다.

관대한 두더지는 고슴도치가 땅굴에 빠져 죽는건 원치 않는다.

우리는 두더지를 위해 몇번 움직여야 가장 빨리 두더지를 땅굴로 사라지게 할 수 있는지 알아보도록 하자.

주의 할 것은 고슴도치와 두더지는 한 칸에서 마주치면 안된다.

고슴도치가 두더지를 꽉 안고 그 가시에  두더지가 찔려 죽기때문이다.

두더지는 장님이라 땅위에서 많이는 못 움직인다. 이동횟수가 10이상이면 -1을 출력한다.

이동은 상하좌우 네 방향으로 이동가능하며 밭 주위는 벽이라고 생각한다.

Input

첫줄에 테스트케이스 T가 들어온다. 
 
다음줄에 R과 C가 들어오고 그 다음줄 부터 R개의 줄에 각 C개의 숫자가 들어온다.
 
(단, R, C는 50 이하의 자연수 이다)
 
1은 벽이고 2는 땅굴 3은 두더지 4는 고슴도치이다.
 
도슴도치와 두더지는 한마리씩 존재한다.  
 
땅굴은 여러 개 있을 수 있다.

Output

고슴도치를 살리되 가장빨리 땅굴로 두더지가 들어가는 이동 횟수를 출력한다.

이동횟수가 10이상이거나 탈출할 방법이 없을 경우 -1출력.

Sample Input

Sample Output

1
5 5
1 1 1 1 1
1 3 0 4 1
1 0 0 0 1
1 2 1 2 1
1 1 1 1 1
3

Source

Sink