Untitled

Game domino
Nam được tham gia vào trò chơi rất phổ biến là game Domino. Tuy nhiên không giống như bình thường, Nam chỉ cần xếp một vài con domino sao cho khi bắt đầu đổ Domino, số Domino bị đổ là nhiều nhất.
Ma trận N*N với 1 là vị trí đã đặt sẵn các con domino, 0 là vị trí còn thiếu các con domino và Nam có quyền đặt các con domino này để điều hướng dòng chảy của domino và được phép đặt tối đa M con domino.
Domino sẽ luôn luôn bắt đầu chạy từ ô 1*1 và chạy sang phải đầu tiên.
Các con domino mà Nam đặt vào có thể điều hướng theo 4 hướng trên, dưới, trái , phải và không được phép đặt vào hướng ngược lại so với dòng chảy hiện tại. 
Domino sẽ đổ tiếp theo hướng hiện tại và chỉ thay đổi hướng khi gặp ô domino do Nam đặt vào và sẽ tiếp tục đổ thẳng tiếp theo hướng đặt vào đó cho đến khi gặp vị trí nam đặt domino (đổ hướng tiếp ) hoặc dừng lại  khi ra ngoài map hay gặp điểm domino đã bị đổ hay gặp ô trống (vị trí 0) mà Nam đã hết Domino có thể đặt.
Hãy giúp Nam đặt domino sao cho số domino đổ là nhiều nhất, và in ra số nhiều nhất đó.
Input:
1                -> số TC
8 5              -> Ma trận N*N, 5 là số Domino tối đa mà Nam có
1 1 0 1 1 1 0 0  -> map đầu vào với 1 là vị trí đã đặt domino
0 0 0 0 0 0 1 0  -> 0 là vị trí Nam có quyền đặt các domino để 
0 0 1 0 0 0 1 0  điều hướng dòng chảy
0 0 1 0 0 0 1 0
0 0 0 1 1 1 0 0
0 0 1 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0
//Giải thích
Domino sẽ luôn luôn bắt đầu chạy từ ô (1,1) và chạy sang phải đầu tiên, như vậy ta sẽ đổ 2 con domino ở vị trí (1,1) và (1,2)
Tiếp đó đến ô (1,3) là vị trí Nam có thể đặt domino, ở đây sẽ có 3 lựa chọn
   + Nam sẽ đặt vào domino đổ theo hướng lên trên -> trò chơi kết thúc -> Tổng số domino có được là 2 (không tính domino mà Nam đặt vào)
   + Nam sẽ đặt domino đi phải tiếp -> Domino sẽ tiếp tục đổ sang ô (1,4), (1,5), (1,6) -> gặp ô (1,7) = 0 Nam sẽ tiếp tục được phép lựa chọn đặt Domino theo hướng nào tiếp theo …
   + Nam sẽ đặt Domino theo hướng xuống dưới -> Do mino sẽ đổ xuống ô (2,3) và tại đây Nam sẽ tiếp tục lựa chọn đặt Domino theo hướng nào tiếp theo
   + ở đây Nam sẽ không được phép đặt Domino theo hướng sang trái vì nó ngược với hướng chảy hiện tại
-> Với những khi gặp ô 0 tiếp theo, Nam sẽ được quyền lựa chọn như ví dụ trên, hãy giúp nam tìm các đặt Domino để số Domino đổ là nhiều nhất.
Với ví dụ trên tại ô (1,3) Nam sẽ đặt domino sang phải, (1,7) xuống dưới, (5,7) sang trái, (5,3) xuống dưới, (8,3) sang phải sau đó Nam đã hết domino để đặt nên sẽ dừng ở ô (8,6), ta sẽ được số domino đổ là nhiều nhất và tổng là 16 domino (Sẽ không tính những domino mà Nam đặt thêm vào).
Giải sử: 2 sang phải, 3 sang trái, 4 lên trên, 5 xuống dưới ta sẽ được cách đặt như sau: màu xanh là vị trí các domino sẽ đổ, màu vàng là vị trí Nam đặt domino.

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

Input:
// Input:
// 3
// 8 5
// 1 1 0 1 1 1 0 0
// 0 0 0 0 0 0 1 0
// 0 0 1 0 0 0 1 0
// 0 0 1 0 0 0 1 0
// 0 0 0 1 1 1 0 0
// 0 0 1 0 0 0 1 0
// 0 0 1 0 0 0 0 0
// 0 0 0 1 1 1 0 0
// 7 5
// 1 1 1 1 1 1 0
// 1 1 1 1 1 1 1
// 1 1 1 1 1 1 1
// 0 1 1 0 1 1 0
// 1 1 1 1 1 1 1
// 1 1 1 1 1 1 1
// 0 1 1 0 1 1 0
// 8 5
// 1 1 0 1 1 1 0 0
// 0 0 0 0 0 0 1 0
// 0 0 1 1 0 0 1 0
// 0 1 0 0 0 0 1 0
// 0 0 1 1 1 1 0 0
// 0 1 0 0 0 0 1 0
// 0 1 0 0 0 0 0 0
// 0 0 1 1 1 1 0 0
// Output:
// 16
// 16
// 18