슬 문제는 구슬이 최소 움직인 수를 구하는 문제이다. 요구 사항은 다음과 같다.

<!--[if !supportEmptyParas]--> <!--[endif]-->

- 빨간 구슬(1)과 파란 구슬(2), 벽(3), 홀(4)이 있다.

- 빨간 구슬이 홀에 들어가면 점수를 얻는다. 파란구슬이 홀에 들어가면 점수를 얻지 못하고 게임이 끝난다.

- 빨간 구슬과 파란 구슬이 동시에 홀에 들어가는 경우에도 점수를 얻지 못하고 게임이 끝난다.

- 빨간 구슬과 파란 구슬이 같은 영역에 있다면 구슬이 부딪혀 깨지게 되어 게임이 끝난다.

- 빨간 구슬과 파란 구슬은 같이 움직이며 홀은 하나 이상이다.

- 만약 점수를 얻지 못하는 경우에는 -1을 출력한다.

- U는 up, D는 down, R은 right, L은 left를 의미한다.

<!--[if !supportEmptyParas]--> <!--[endif]-->

예를 들면, 다음과 같이 있을 때 회색 영역은 벽, x는 홀을 의미한다. 벽에 막혀 있는 곳에는 갈 수가 없으며 직사각형의 외부 영역으로 나갈 수 없다.


<!--[endif]-->

<!--[if !supportEmptyParas]--> 

<!--[endif]-->

이 때, 아래(D)로 두 번 이동하게 되면 파란 구슬도 홀에 들어가게 되므로 점수를 얻을 수 없다. 점수를 얻을 수 있는 경우는 다음과 같다.

오른쪽(R), 아래(D), 아래(D), 왼쪽(L)으로 이동하면 빨간 구슬만 홀에 들어가고 파란 구슬은 홀에 들어가지 않는다. 그러므로 구슬의 최소 움직임은 4이다.

<!--[if !supportEmptyParas]--> <!--[endif]-->

입력

첫째 줄 : 케이스 수(T)

둘째 줄 : 직사각형의 row, column 수

셋째 줄 : 직사각형 영역에 맞게 구슬과 홀의 위치가 주어짐.

<!--[if !supportEmptyParas]--> <!--[endif]-->

출력 : #케이스번호 최소 움직인 수

<!--[if !supportEmptyParas]--> <!--[endif]-->

입력 예제)

1

7 9

3 3 3 3 3 3 3 3 3

3 0 0 0 0 0 0 0 3

3 0 2 0 3 0 1 0 3

3 0 0 3 3 0 0 0 3

3 0 4 0 0 0 4 0 3

3 0 0 0 0 0 0 0 3

3 3 3 3 3 3 3 3 3

<!--[if !supportEmptyParas]--> <!--[endif]-->

출력 예제)

#1 4 



------------------------------------------------------------------------------------------------------

이거 recursive로 푸는건 알겠는데

인사이트 좀 더주세요ㅠㅠ