Qua Cau
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);
}
}
}