Untitled
unknown
plain_text
a month ago
2.0 kB
0
Indexable
Never
///tttt #include <iostream> using namespace std; const int MAX_N = 4; int N; char board[MAX_N][MAX_N]; int maxRooks; // Biến lưu trữ kết quả số lượng Rook tối đa bool rowOccupied[MAX_N]; // Đánh dấu hàng đã bị chiếm bool colOccupied[MAX_N]; // Đánh dấu cột đã bị chiếm bool isSafe(int row, int col) { if (rowOccupied[row] || colOccupied[col]) { return false; } // Kiểm tra các ô trên cùng hàng và cột từ [0 đến col-1] và [row-1 đến 0] có tường 'X' không for (int i = col - 1; i >= 0; i--) { if (board[row][i] == 'X') break; if (colOccupied[i]) return false; } for (int i = row - 1; i >= 0; i--) { if (board[i][col] == 'X') break; if (rowOccupied[i]) return false; } return true; } void backtrack(int placedRooks, int row) { if (row == N) { if (placedRooks > maxRooks) { maxRooks = placedRooks; } return; } for (int col = 0; col < N; col++) { if (board[row][col] == '.' && isSafe(row, col)) { // Đặt Rook rowOccupied[row] = true; colOccupied[col] = true; backtrack(placedRooks + 1, row + 1); // Gỡ Rook rowOccupied[row] = false; colOccupied[col] = false; } } // Không đặt Rook ở dòng này, chuyển sang dòng tiếp theo backtrack(placedRooks, row + 1); } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> board[i][j]; } } maxRooks = 0; for (int i = 0; i < N; i++) { rowOccupied[i] = false; colOccupied[i] = false; } backtrack(0, 0); cout << "Case #" << tc << endl << maxRooks << endl; } return 0; }
Leave a Comment