#include #include using namespace std; // Check if any two rooks are threatening each other. bool isValid(const vector& board) { // First we are going to see if any horizontal threats exist for (unsigned int i = 0; i < board.size(); i++) { // Start out assuming nothing is threatening (since we haven't seen // anything to the contrary) bool threat = false; // Now loop through the columns of this row for (unsigned int j = 0; j < board.size(); j++) { // If we find a rook then we are threatening the rest of the row if (board[i][j] == 'R') { // If we were already threatened, then there is a problem. if (threat) return false; threat = true; } // If we find a wall, then it is OK if we find another rook on // the other side of it if (board[i][j] == 'X') threat = false; } } // Now we check for vertical threats. for (unsigned int i = 0; i < board.size(); i++) { // Start out assuming nothing is threatening (since we haven't seen // anything to the contrary) bool threat = false; for (unsigned int j = 0; j < board.size(); j++) { // If we see a rook then we are threatening the rest of the column if (board[j][i] == 'R') { // If we were already threatened, then there is a problem if (threat) return false; threat = true; } // If we find a wall, then it is OK if we find another rook on // the other side of it if (board[j][i] == 'X') threat = false; } } // No problems here, we're done return true; } // Find how many rooks we can place on this board, assuming the // first spot we need to examine is at (x, y). int rooks(vector&board, unsigned int x, unsigned int y) { // If we have looped onto a new row if (x == board.size()) { x = 0; y++; } // If we have looped off the end of the board. if (y == board.size()) { // Count up how many we placed int count = 0; for (unsigned int i = 0; i < board.size(); i++) { for (unsigned int j = 0; j < board[i].size(); j++) { if (board[i][j] == 'R') count++; } } // We are done return count; } // If this spot is a wall, then skip on to the next if (board[x][y] == 'X') return rooks(board, x + 1, y); // Check this spot board[x][y] = 'R'; int temp; // If it is valid to add a rook here if (isValid(board)) // Find out how many rooks we could add counting that one temp = rooks(board, x + 1, y); else // Otherwise, ignore the possibility of placing a rook here temp = 0; // Set this spot back to empty board[x][y] = '.'; // Return the best of what we've seen so far and filling in the board // with the current spot empty. return max(temp, rooks(board, x + 1, y)); } int main() { // How large is the board? (The boards are all square.) int n; while (cin >> n && n) { // Read in the board vector board; board.resize(n); for (int i = 0; i < n; i++) { cin >> board[i]; } // Print out the answer. cout << rooks(board, 0, 0) << endl; } }