Qua Cau

 avatar
unknown
plain_text
2 years ago
8.1 kB
6
Indexable
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


########################################
input
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



#######################################
code
package QuaCau;

import java.io.FileInputStream;
import java.util.Scanner;

public class quaCau {
	static int[][] matrix;
	static int[] dy = { -1, 0, 1 };
	static int M = 5;
	static int N;
	static int ans;

	static void move(int x, int y, int live, int sum) {
		if (x == 0) {
			if (ans < sum) ans = sum;
			return;
		}
		x--;
		for (int i = 0; i < 3; i++) {
			int y1 = y + dy[i];
			if (y1 >= 0 && y1 < 5) {
				if (matrix[x][y1] < 2) {
					move(x, y1, live, sum + matrix[x][y1]);
				} else {
					if (live == 1) {
						move(x, y1, 0, sum);
					}
				}
			}
		}
	}

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("D://Trainee//SRV_training//src//QuaCau//quaCau.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			M = 5;
			N = sc.nextInt();
			matrix = new int[N + 1][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			ans = -1;
			move(N, 2, 1, 0);
			System.out.println("#" + test_case + " " + ans);
		}

	}

}