Untitled

Qua Cầu


Có 1 số cây cầu làm bằng gỗ. Trải qua 1 thời gian,những  cây cầu trở nên hư hại và xuất hiện những lỗ thủng trên đó. Được biết những cây cầu đó luôn có độ rộng M = 5(bước đi) và độ dài trong khoảng3<n<=12 font="" <="" đi).="" (bước="" style="margin: 0px; padding: 0px;"></n<=12>
Công việc:
Có 1 người luôn luôn đứng giữa ở 1 phía của cây cầu. Nhiệm vụ của bạn là phải đưa người đó qua được cầu với số đồng xu nhặt được là lớn nhất. Được biết trên cầu có 1 số đồng xu bị đánh rơi và người đó chỉ có thể đi thẳng, đi chéo trái hoặc đi chéo phải. Ngoài ra người đó có mang 1 tấm ván. Nó có thể vá được 1 lỗ thủng trên cầu giúp người đó có thể đi qua được.
Lưu ý : không có nhiều hơn 1 đồng xu tại 1 địa điểm.
 
Input
Dòng đầu tiên là số lượng trường hợp thử nghiệm.
Dòng thứ 2 chiều dài của cây cầu (N).
N dòng tiếp theo mô tả cây cầu theo ma trận 2 chiều. Trong đó: ‘0’ là có thể đi được, ‘1’ là có đồng xu(có thể đi được)và ‘2’ là lỗ thủng.
 
Output
In theo định dạng  “#test_case” và số đồng xu nhiều nhất có thể khi qua đươc cầu.
Nếu không thể qua cầu in ra  -1.


 


Sample

Input

3

7

1 2 0 1 0

0 0 2 0 1

0 1 0 2 1

1 0 0 0 1

0 0 0 2 2

2 0 1 0 1

0 1 2 2 0

10

2 2 2 2 0

1 2 0 0 2

0 2 0 0 0

2 2 0 2 2

0 2 2 2 0

0 0 0 0 0

1 0 0 0 2

0 0 0 0 0

2 2 0 2 1

0 2 2 2 0

9

0 2 1 1 2

0 2 2 2 2

2 2 2 1 0

0 0 2 0 2

0 2 2 1 0

1 0 2 2 2

2 2 0 2 0

2 2 2 0 2

0 0 2 0 0

 

Output

#1 6

#2 -1

#3 0



Code:
#include<iostream>
using namespace std;

int a[20][5];

int X[3] = { 1,-1, 0};
int Y[3] = {-1,-1, -1};

int ans;
int n;


void Try(int row, int col, int plank, int sum){
	
	if(row ==0){
		if (ans < sum )ans = sum;
		return;
	}
	for(int h =0; h<3; h++){
		int r = row +Y[h];
		int c = col +X[h];
		
		if(r >=0 && r<n && c>=0 && c<5){

			if ( a[r][c] <2 ){
				Try(r, c, plank, sum + a[r][c]);
			}
			else{
				if(plank){
					Try(r,c,0,sum);
				}
			}
		}
	}
	
		
}

int main(){
	freopen("text.txt", "r", stdin);
	int test;
	cin >> test;
	//freopen("text.txt", "r", stdin);
	for(int tc= 1; tc <= test; tc++){
		
		cin >> n;

		for(int i=0; i < n; i++){
			for(int j= 0; j < 5; j++){
				cin >> a[i][j];
			}
		}
		
		ans =-1;
		Try(n, 2, 1, 0);
		cout << "#" << tc << " " << ans << endl;
		}
	return 0;
}