Untitled

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