Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
8.2 kB
2
Indexable
Never
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

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

50
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 
9
2 2 1 1 1 
1 1 2 0 1 
0 0 2 0 0 
0 2 1 2 0 
0 2 1 1 0 
2 0 1 1 2 
0 2 0 0 2 
1 0 2 2 2 
1 1 0 0 1 
9
1 1 0 1 1 
0 0 0 0 0 
0 1 0 0 2 
2 1 1 1 2 
2 2 1 1 0 
0 1 0 2 2 
1 2 0 1 0 
0 1 0 0 2 
1 2 1 0 0 
9
1 1 1 1 2 
0 1 1 1 2 
1 1 1 1 2 
0 2 2 2 2 
1 0 2 1 1 
1 2 0 1 0 
1 0 1 2 0 
1 0 2 0 0 
0 1 0 0 1 
9
1 2 2 0 1 
0 0 0 0 0 
2 1 2 1 1 
0 2 2 0 0 
2 2 1 1 2 
1 0 0 1 0 
0 2 0 0 1 
0 2 1 1 1 
2 2 1 0 2 
6
0 2 2 1 0 
2 0 1 0 0 
1 2 1 2 2 
2 2 0 1 0 
0 1 1 2 1 
0 1 2 0 1 
6
0 1 1 2 1 
0 2 0 2 2 
0 0 2 1 2 
0 2 0 1 1 
0 1 0 1 0 
1 0 0 2 2 
6
0 0 0 1 0 
0 2 1 2 0 
1 2 0 1 2 
2 2 1 1 2 
1 2 2 1 1 
1 2 1 1 2 
6
1 1 0 2 1 
2 2 1 2 2 
1 1 2 1 2 
0 1 2 0 0 
0 1 0 0 0 
0 1 2 2 2 
6
2 1 2 1 1 
2 2 2 1 1 
1 2 0 1 1 
0 1 2 1 0 
2 0 1 0 0 
0 0 2 0 1 
7
2 2 0 0 0 
0 2 0 0 1 
2 2 0 2 2 
2 1 2 2 0 
1 0 2 1 1 
0 1 1 0 2 
0 0 1 0 2 
7
2 0 0 1 0 
2 1 1 1 1 
0 0 0 2 2 
0 2 1 2 1 
1 0 0 1 0 
0 2 2 2 0 
1 1 0 1 2 
7
2 2 0 2 2 
0 1 0 1 0 
1 1 0 2 0 
2 2 2 1 2 
1 0 2 2 1 
0 0 0 0 2 
0 0 2 2 1 
7
0 0 0 2 2 
1 2 2 1 1 
2 0 2 0 2 
1 1 2 0 0 
0 0 2 2 0 
2 2 1 0 2 
1 1 1 2 1 
7
1 0 2 2 0 
1 0 0 2 1 
1 0 2 2 2 
2 0 1 1 0 
0 2 0 1 2 
0 0 0 1 2 
1 0 0 0 0 
7
1 0 1 1 2 
2 1 0 0 0 
0 0 2 1 1 
2 2 0 0 0 
1 0 2 2 2 
0 1 0 1 0 
0 2 1 0 1 
7
2 0 0 2 1 
1 1 0 0 1 
1 1 0 2 2 
2 0 0 2 1 
0 2 2 1 0 
2 0 2 0 1 
0 1 1 2 2 
7
2 1 0 1 2 
0 0 0 1 0 
2 1 2 0 2 
2 2 0 1 2 
2 0 0 0 2 
2 1 0 0 0 
2 1 2 1 2 
8
0 0 2 0 2 
0 0 0 2 2 
1 0 1 1 0 
2 2 2 1 2 
0 2 0 2 1 
1 0 0 2 0 
2 0 0 2 1 
0 2 0 0 1 
8
1 0 0 2 1 
0 1 0 1 0 
2 0 1 2 0 
1 2 2 1 0 
0 0 2 2 2 
0 2 1 2 0 
0 0 0 1 2 
2 2 2 1 1 
8
2 2 2 0 2 
2 0 2 1 2 
2 1 0 0 0 
1 1 1 0 0 
1 2 0 1 2 
2 0 2 2 1 
2 1 1 0 1 
0 1 0 1 0 
8
1 1 2 0 0 
1 2 0 2 1 
2 1 1 0 0 
1 2 0 0 1 
1 2 0 0 2 
1 2 2 2 2 
1 0 2 1 1 
2 0 1 1 0 
8
2 2 1 1 2 
0 1 2 0 0 
1 2 2 2 2 
2 2 2 2 2 
2 2 0 0 1 
0 2 2 1 0 
0 1 2 1 1 
2 1 0 0 1 
5
1 2 2 2 0 
1 2 0 0 1 
2 2 1 1 0 
1 0 2 1 0 
2 1 0 1 2 
5
0 1 0 2 1 
1 1 1 0 2 
1 1 2 2 0 
0 2 1 2 1 
0 2 2 1 0 
5
0 1 1 1 0 
0 0 0 0 2 
0 2 2 2 1 
0 1 1 1 1 
0 1 2 2 1 
5
0 2 0 0 2 
0 0 0 2 1 
0 1 2 0 2 
2 2 2 1 2 
0 1 1 2 2 
5
2 2 1 2 0 
1 2 1 2 0 
2 1 1 2 0 
0 2 1 1 0 
1 2 1 0 0 
10
1 2 1 0 0 
2 1 1 2 1 
0 0 2 1 0 
0 0 2 1 0 
1 2 0 2 0 
2 1 2 2 2 
0 1 1 1 0 
0 1 1 1 1 
1 2 2 1 2 
0 2 1 0 0 
10
1 0 2 2 0 
1 0 2 0 0 
1 2 0 0 1 
1 1 1 0 2 
1 1 2 2 0 
0 0 0 0 2 
2 2 1 1 0 
0 0 0 2 1 
0 1 0 0 0 
2 1 0 2 1 
10
2 1 2 0 0 
1 2 0 0 2 
2 0 1 2 0 
2 0 2 2 2 
1 1 0 1 1 
1 2 1 1 0 
1 1 2 2 1 
1 0 1 2 1 
1 1 1 2 1 
1 0 0 2 1 
10
0 0 1 0 0 
1 0 2 2 1 
2 1 1 2 1 
1 1 1 0 1 
0 0 1 1 2 
2 2 2 1 0 
0 2 1 0 0 
2 2 1 0 2 
2 2 2 0 2 
1 1 2 1 0 
10
0 0 0 1 0 
0 2 2 1 0 
2 1 1 1 1 
1 0 1 2 0 
1 1 0 1 0 
0 2 2 1 2 
0 1 0 2 2 
0 1 1 2 2 
1 1 0 1 1 
2 0 2 1 1 
11
0 0 0 2 1 
1 1 0 0 2 
2 0 2 2 0 
0 1 1 1 2 
2 0 1 0 2 
0 0 0 1 1 
0 1 1 1 0 
0 2 2 1 2 
0 2 2 0 2 
2 1 1 0 0 
0 2 1 0 0 
11
2 0 1 2 0 
1 0 0 0 1 
0 1 2 2 2 
2 1 1 0 2 
2 0 2 2 0 
2 2 1 0 1 
1 1 0 0 2 
0 1 2 0 1 
2 0 1 2 1 
2 2 0 0 0 
2 0 1 0 0 
11
2 1 1 0 2 
1 1 0 2 2 
2 0 2 1 1 
2 1 2 1 0 
2 2 2 2 1 
1 2 1 1 1 
0 0 1 2 2 
0 0 1 2 2 
0 0 2 2 0 
0 1 0 2 2 
2 1 1 1 1 
11
2 0 0 2 0 
0 1 0 0 0 
0 2 1 0 0 
2 0 0 0 2 
0 0 0 2 2 
1 1 0 2 1 
1 0 2 0 1 
2 0 1 0 2 
1 2 1 2 0 
0 0 0 0 1 
2 1 0 2 2 
11
1 1 1 1 0 
1 1 0 0 0 
2 0 1 2 2 
1 2 0 1 2 
2 0 0 1 2 
2 1 1 2 0 
1 0 1 2 0 
2 2 2 1 2 
0 0 2 1 0 
1 0 2 2 0 
2 2 0 1 0 
12
0 2 1 0 1 
1 1 0 2 0 
2 1 0 1 0 
2 2 0 1 2 
0 2 0 0 2 
1 2 2 1 1 
0 1 0 0 0 
1 2 2 0 1 
0 0 1 1 0 
2 0 2 0 0 
1 2 2 0 2 
0 0 1 1 0 
12
1 2 2 0 0 
0 2 2 1 2 
1 1 2 1 2 
2 0 0 2 2 
2 1 0 0 0 
1 2 2 1 2 
1 1 0 1 0 
1 2 2 2 0 
0 1 1 2 1 
1 2 2 2 0 
2 2 2 2 2 
0 2 2 2 1 
12
1 1 2 0 0 
2 0 0 1 1 
2 1 2 0 1 
1 0 2 0 0 
2 0 1 2 0 
2 2 0 0 1 
0 1 1 2 1 
1 2 0 0 0 
0 2 1 2 0 
0 2 1 2 1 
2 0 0 0 1 
1 0 2 0 1 
12
2 2 0 0 0 
2 0 0 0 1 
1 0 0 0 0 
1 0 1 1 0 
1 1 1 1 2 
0 1 2 2 2 
1 0 2 0 1 
0 1 2 0 1 
2 0 0 0 2 
0 1 2 2 1 
0 2 2 0 1 
0 1 0 0 0 
12
2 1 1 1 2 
2 1 0 0 1 
1 1 1 1 0 
2 1 0 0 0 
0 1 2 0 0 
1 1 0 1 2 
2 1 2 0 2 
2 1 1 1 0 
1 1 1 2 1 
2 1 1 2 1 
2 1 2 2 1 
0 1 0 2 0 
4
1 2 2 2 2 
0 2 2 2 0 
0 2 0 2 1 
0 2 0 2 0 
4
2 0 0 0 1 
2 2 2 2 2 
1 0 2 0 2 
2 0 2 1 2 
4
0 2 2 1 1 
0 2 1 0 1 
1 0 0 1 2 
1 0 2 0 1 
4
2 1 0 0 0 
0 2 2 2 0 
1 0 2 0 1 
1 2 2 1 1 
4
0 2 0 1 0 
1 1 1 2 2 
1 1 2 1 1 
2 2 1 1 1


#include <iostream>
#define MAX 0;
using namespace std;

int n, m = 5;
int arr[101][101];
int dR[3] = {-1, -1, -1};
int dC[3] = {-1, 0, 1};
int visited[101][101];
int cost;
int Max;
int lt;
bool flag;

void BackTrack(int i, int j){

	if(lt <= 1){
		if(i == 0){
			Max = max(Max, cost);
			flag = true;
		}
	}

	for(int k=0; k<3; k++){
		int x = i + dR[k];
		int y = j + dC[k];

		if(x>=0 && x<n && y>=0 && y<m && visited[x][y] == 0){
			visited[x][y] = 1;

			if(arr[x][y] == 1)
				cost += 1;
			else if(arr[x][y] == 2)
				lt += 1;
			
			BackTrack(x, y);

			if(arr[x][y] == 1)
				cost -= 1;
			else if(arr[x][y] == 2)
				lt -=1;

			visited[x][y] = 0;
		}
	}
}

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

		cin >> n;
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				cin >> arr[i][j];
			}
		}

		for(int i=0; i<n+1; i++){
			for(int j=0; j<m; j++){
				visited[i][j] = 0;
			}
		}

		for(int i=0; i<m; i++){
			arr[n][i] = 2;
		}

		arr[n][2] = 0;

		n+=1;

		cost = 0;
		lt = 0;
		visited[n-1][2] = 1;
		Max = MAX;
		flag = false;

		BackTrack(n-1, 2);

		cout << "#" << tc << " ";
		if(flag)
			cout << Max << endl;
		else
			cout << "-1" << endl;

	}
	return 0;
}