Official

C - Avoid Rook Attack Editorial by en_translator


This problem can be solved by the following two approaches:

  1. Inspect each square to check if it is never covered by any pieces
  2. Inspect each piece to enumerate the squares it covers

We will explain these approaches.

1. Check if each square is never covered by any pieces

A square is covered by a piece if and only if there is a piece in the same row or column.

We can implement this condition and apply it to each cell to solve this problem.

The sample code follows.

#include <array>
#include <iostream>

using namespace std;

// Check if one can place a piece on square (i, j)
bool check_square(const array<array<bool, 8>, 8> &board, int i, int j) {
    for (int k = 0; k < 8; k++) {
        // If there is already a piece on the same row, one cannot use this square
        if (board[i][k]) {
            return false;
        }
    }
    for (int k = 0; k < 8; k++) {
        // If there is already a piece on the same column, one cannot use this square
        if (board[k][j]) {
            return false;
        }
    }
    return true;
}

int main() {
    array<array<bool, 8>, 8> board;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            char c;
            cin >> c;
            board[i][j] = c == '#';
        }
    }

    int ans = 0;

    // For each square,
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            // Increment the answer by one if one can use this square
            if (check_square(board, i, j)) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}
# Check if one can place a piece on square (i, j)
def check_square(board, i, j):
    for b in board[i]:
        # If there is already a piece on the same row, one cannot use this square
        if b:
            return False

    for row in board:
        # If there is already a piece on the same column, one cannot use this square
        if row[j]:
            return False
    return True

board = [[c == '#' for c in input()] for i in range(8)]

ans = 0

# For each square,
for i in range(8):
    for j in range(8):
        # Increment the answer by one if one can use this square
        if check_square(board, i, j):
            ans += 1

print(ans)

2. Enumerate the squares covered by each piece

Prepare an empty grid. For each piece, paint the squares belonging to the same row or column. After this operation, count unpainted squares to obtain the answer.

The sample code follows.

#include <algorithm>
#include <array>
#include <iostream>
#include <ranges>

using namespace std;

int main() {
    array<array<bool, 8>, 8> board;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            char c;
            cin >> c;
            board[i][j] = c == '#';
        }
    }

    // We will store whether each square is covered
    array<array<bool, 8>, 8> safe{};
    // Initialize with true
    ranges::fill(safe | views::join, true);

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            // If this cell has a piece,
            if (board[i][j] == 1) {
                // one cannot use the squares in the same row
                for (int k = 0; k < 8; k++) {
                    safe[i][k] = false;
                }
                // one cannot use the squares in the same column
                for (int k = 0; k < 8; k++) {
                    safe[k][j] = false;
                }
            }
        }
    }

    // Print the number of squares that can be used
    cout << ranges::count(safe | views::join, true) << endl;
    return 0;
}
board = [[c == '#' for c in input()] for i in range(8)]

# We will store whether each square is covered
# Initialize with true
safe = [[True for i in range(8)] for j in range(8)]

for i, row in enumerate(board):
    for j, b in enumerate(row):
        # If this cell has a piece,
        if b:
            for k in range(8):
                # one cannot use the squares in the same row
                safe[i][k] = False
                # one cannot use the squares in the same column
                safe[k][j] = False

# Print the number of squares that can be used
print(sum(+f for row in safe for f in row))

posted:
last update: