Untitled
unknown
plain_text
a year ago
2.1 kB
2
Indexable
Never
package APS2; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class ChessRook { static int N; static int[][] board; static int maxRook; public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("src\\APS2\\ChessRook_input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); board = new int[N][N]; for (int i = 0; i < N; i++) { String line = sc.next(); for (int j = 0; j < N; j++) { if (line.charAt(j) == 'X') { board[i][j] = 1; // o co tuong } } } maxRook = 0; Solve(0, 0); System.out.println("Case #" + tc); System.out.println(maxRook); } // for tc } public static void Solve(int row, int countRook) { if (countRook > maxRook) { maxRook = countRook; // return; } for (int i = row; i < board.length; i++) { // dat rook theo hang for (int j = 0; j < board[0].length; j++) { if (isSafe(i, j)) { board[i][j] = 2; // dat xe = 2 Solve(i, countRook + 1); board[i][j] = 0; } } } } static boolean isSafe(int row, int col) { if (board[row][col] == 1 || board[row][col] == 2) { // la tuong hoc da // co xe return false; } // cung cot, hang ben tren for (int i = row; i >= 0; i--) { if (board[i][col] == 2) { // gap xe truoc -> false return false; } else if (board[i][col] == 1) { // gap tuong, break de xet tiep cac // dieu kien sau, co kha nang // thoa man break; } } // cung hang, cot ben trai for (int i = col; i >= 0; i--) { if (board[row][i] == 2) { return false; } else if (board[row][i] == 1) { break; } } // cung hang, cot ben phai for (int i = col; i < board[0].length; i++) { if (board[row][i] == 2) { return false; } else if (board[row][i] == 1) { break; } } return true; } }