# Untitled

unknown
plain_text
22 days ago
2.1 kB
0
Indexable
Never
```public class Solution {
static final int M = 5;
static int[][] map;
static int[][] visited;
static int Ans = 0;
static int nvan = 0;

static int[] dx = { -1, -1, -1 };
static int[] dy = { -1, 0, 1 };

public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
int n = sc.nextInt();
Ans = -1;
nvan = 1;

map = new int[n][M];
visited = new int[n][M];
for (int i = 0; i < n; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
}
}

backtrack(n, 2, 0, 0);

System.out.println("#" + tc + " " + Ans);
}
}

private static void backtrack(int row, int col, int step, int coin) {
// dieu kien dung
if (step == map.length) {
Ans = Math.max(Ans, coin);
return;
}

for (int i = 0; i < 3; i++) {
int xx = row + dx[i];
int yy = col + dy[i];
if (isSafe(xx, yy)) {
if (visited[xx][yy] == 0) {
if (map[xx][yy] == 0) {
visited[xx][yy] = 1;
backtrack(xx, yy, step + 1, coin);
visited[xx][yy] = 0;
}

if (map[xx][yy] == 1) {
visited[xx][yy] = 1;
backtrack(xx, yy, step + 1, coin + 1);
visited[xx][yy] = 0;
}

if (map[xx][yy] == 2) {
if (nvan == 1) {
for (int j = 0; j <= 1; j++) {
if (j == 0) {
nvan = 0;
visited[xx][yy] = 1;
backtrack(xx, yy, step + 1, coin);
nvan = 1;
visited[xx][yy] = 0;
}
}
}
}
}
}
}
}

private static boolean isSafe(int xx, int yy) {
if (xx >= 0 && xx < map.length && yy >= 0 && yy < map[0].length) {
return true;
}
return false;
}
}

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