Giải bài trực tuyến

Dạo này kinh tế suy thoái nên học bổng cũng ít đi khiến cho sơncbg phải nghĩ ra cách tiết kiệm các chi phí của bản thân và việc tiết kiệm tiền điện thoại cũng là đưong nhiên. Cách làm thông dụng nhất hiện nay là mua thêm 1 chiếc điện thoại khác và mua sim khuyến mãi để gọi và nhắn tin (2 tay 2 súng^^ : 1 máy nghe 1 máy gọi). Nghe bạn bè quảng cáo rằng Vinaphone rất nhiều khuyến mại mà giá máy ban đầu lại rẻ nên sơncbg quyết định mua 1 chiếc máy alo của Vinaphone ^^. Mua máy về rồi thì tất nhiên là phải nghịch^^ và sơncbg phát hiện ra rằng trên máy có 1 game giống với game IQ trên dos mà hồi bé mình thường chơi đó là BOXMAN. Trò chơi này được mô tả như sau :

Cho 1 bản đồ kích thước M*N, trên bản đồ có các thùng gỗ( có thể đẩy để di chuyển được), các bức tường( là chướng ngại vật và không thể di chuyển được), và 1 số mục tiêu. Bạn đang ở 1 vị trí cho trước nào đó trên bản đồ. Nhiệm vụ của bạn là phải đẩy các tất cả các thùng gỗ đè lên tất cả các mục tiêu( số thùng gỗ = số mục tiêu).

Vì ngồi ở cuối lớp nên sơncbg và 1 người bạn thân của mình thường xuyên chơi trò này trong giờ. Hai người ngồi dò mãi cũng chỉ chơi được đến mức 15/70. Nản quá nên sơncbg quyết định phải lập trình để chơi cho đỡ vất vả^^( không thì vất vả quá^^). Bạn hãy giúp sơncbg nhé!

Input

-         dòng đầu ghi hai số M, N(M, N <= 6)

-         M dòng sau mỗi dòng sau mỗi dòng ghi N số biểu diễn bản đồ với quy cách :

               + 0 là khoảng trống trên bản đồ và bạn có thể di chuyển các thùng gỗ cũng như chính bản thân mình^^ vào đó

               + 1 là vị trí ban đầu bạn đang đứng

               + 2 là vị trí của bức tường(chướng ngại vật)

               + 3 là vị trí của các thùng gỗ

( ở bản đồ này không ghi vị trí các mục tiêu)

-         M dòng tiếp theo mỗi dòng ghi N số : các mục tiêu ghi số 3 còn lại ghi số 0

Output

-         Ghi ra số bước đẩy hộp ít nhất để hoàn thành trò chơi

Example

Input:
3 3
1 0 0
3 3 3
0 0 0
0 0 0
0 0 0
3 3 3

Output:
3

Input: 
5 5
0 0 0 1 0
0 2 0 2 0
0 0 0 3 0
0 3 3 0 2
0 0 2 2 2
0 0 3 0 0
0 0 3 0 0
0 0 0 0 0
3 0 0 0 0
0 0 0 0 0
Output:
18

Chú ý rằng muốn đẩy được thùng gỗ thì các bạn phải đứng ở sau thùng gỗ đấy nhé!
Mọi thắc mắc về đề bài liên hệ soncbg