Untitled

skyforce
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SkyForce {
	static int N, map[][], ans, visit[][];
	static int dx[] = { -1, -1, -1 };
	static int dy[] = { -1, 0, 1 };

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("SkyForce"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			map = new int[N][5];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			visit = new int[N][5];
			ans = -1;
			for (int i = 0; i <= 5; i++)// chi tha bom trong doan nay
			{
				BT(N, 2, 0, i); // truyen bom i
			}
			System.out.println("Case #" + tc);
			System.out.println(ans);
		}
	}

	public static void BT(int x, int y, int xu, int bom) { // int bom: gsu vi
															// tri tha bom
		if (x <= 0) {
			// if (xu < 0)
			// return;
			// else {
			ans = Math.max(ans, xu);
			return;
			// }
		}
		if (xu < 0)
			return;
		for (int i = 0; i < 3; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 0 && xx < N && yy >= 0 && yy < 5) {
				if (map[xx][yy] == 0)
					BT(xx, yy, xu, bom);
				else if (map[xx][yy] == 1)
					BT(xx, yy, xu + 1, bom);
				else {
					if (xx >= bom && xx < bom + 5) // gia su tha bom tai xx
													// >=bom!
						BT(xx, yy, xu, bom);
					else
						// k tha bom tru quan dich
						BT(xx, yy, xu - 1, bom);

				}

			}
		}

	}
}

// cach 2

package LuyenDe;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Skyforce {
	static int dx[] = { -1, -1, -1 };
	static int dy[] = { -1, 0, 1 };
	public static int N, M, ans;
	public static int[][] board, visit;

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("skyForce"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int tc = 0; tc < T; tc++) {
			N = sc.nextInt();
			board = new int[N+1][5];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					board[i][j] = sc.nextInt();
				}
			}
			ans = 0;
			visit = new int[N][5];
//			boolean hasBom = true;
			backtrack(N, 2, true, 0, 0);
			System.out.println(ans);

		}

	}

	public static void backtrack(int x, int y, boolean bom, int sum, int mana) {
		if (x <= 0) {
			ans = Math.max(ans, sum);
			return;
		}
		if (y > 4 || y < 0)
			return;

		if (board[x][y] == 1)
			++sum ;
		else if (board[x][y] == 2 && mana <= 0) {
			if (sum > 0)
				--sum;
			else {
				return;// over game
			}
		}
		mana--;

		for (int i = 0; i < 3; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 0 && xx < N && yy >= 0 && yy < 5) {
				if (visit[xx][yy] == 0) {
					visit[xx][yy] = 1;
					backtrack(xx, yy, true, sum, mana);
					if (bom) {
						backtrack(xx, yy, false, sum, 5);
					}
					visit[xx][yy] = 0;
				}
			}
		}
	}
}