quacau
minha
unknown
java
a year ago
7.1 kB
11
Indexable
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
public static int n, res, sX, sY;
public static int[][] matrix;
public static int[][] visited;
public static int[] moveX = { -1, -1, -1 };
public static int[] moveY = { -1, 0, 1 };
public static boolean quaDuoc;
public static boolean check(int x, int y, int van) {
if (matrix[x][y] == 2 && van ==0) {
return false;
}
return true;
}
public static void backtrack(int x, int y, int coin, int van) {
// System.out.println(x+" "+y+" "+van);
if (x == 0) {
if (coin > res) {
res = coin;
}
quaDuoc = true;
return;
}
for (int i = 0; i < 3; i++) {
int newX = x + moveX[i];
int newY = y + moveY[i];
if (newX >= 0 && newY >= 0 && newY < 5 && newX<n && check(newX, newY, van)
&& visited[newX][newY] == 0) {
visited[newX][newY] = 1;
int tmp = 0;
if (matrix[newX][newY] == 1) {
tmp = 1;
}
int w = 0;
if (matrix[newX][newY] == 2) {
w=1;
}
backtrack(newX, newY, coin + tmp, van-w);
visited[newX][newY] = 0;
}
}
}
public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream("D:/LeCongMinh/B8/QuaCau/input.txt"));
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
for (int t = 1; t <= tc; t++) {
n = sc.nextInt();
matrix = new int[n][5];
visited = new int[n][5];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 5; j++) {
matrix[i][j] = sc.nextInt();
}
}
quaDuoc = false;
res = 0;
backtrack(n, 2, 0, 1);
if(!quaDuoc){
System.out.println("#" + t + " " + -1);
}else{
System.out.println("#" + t + " " + res);
}
}
sc.close();
}
}
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
#1 6
#2 -1
#3 0
#4 7
#5 8
#6 8
#7 7
#8 6
#9 4
#10 6
#11 6
#12 5
#13 4
#14 5
#15 3
#16 4
#17 5
#18 5
#19 5
#20 5
#21 4
#22 7
#23 6
#24 7
#25 5
#26 4
#27 5
#28 3
#29 3
#30 5
#31 9
#32 8
#33 7
#34 8
#35 9
#36 8
#37 8
#38 9
#39 6
#40 10
#41 7
#42 -1
#43 6
#44 8
#45 12
#46 1
#47 2
#48 3
#49 2
#50 4
Editor is loading...
Leave a Comment