Qua Cau
unknown
plain_text
2 years ago
8.1 kB
7
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); } } }
Editor is loading...