公式
C - Avoid Rook Attack 解説 by en_translator
This problem can be solved by the following two approaches:
- Inspect each square to check if it is never covered by any pieces
- 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))
投稿日時:
最終更新: