公式
C - Avoid Rook Attack 解説
by
C - Avoid Rook Attack 解説
by
MMNMM
この問題は、次の \(2\) つの方針で解くことができます。
- それぞれのマスについて、どのコマからも取られないか判定する
- それぞれのコマについて、取ることができるマスを計算する
それぞれの方針について解説します。
1. マスごとに取られないか判定する
あるマスがどれかのコマによって取られるということは、同じ行にコマがあるか、同じ列にコマがあるということです。
この条件を実装し、すべてのマスについて確認を行うことでこの問題を解くことができます。
実装例は以下のようになります。
#include <array>
#include <iostream>
using namespace std;
// マス (i, j) にコマを置くことができるか判定する
bool check_square(const array<array<bool, 8>, 8> &board, int i, int j) {
for (int k = 0; k < 8; k++) {
// すでに同じ行にコマが置かれていたら、コマを置くことはできない
if (board[i][k]) {
return false;
}
}
for (int k = 0; k < 8; k++) {
// すでに同じ列にコマが置かれていたら、コマを置くことはできない
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 (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
// コマが置けるなら答えを 1 増やす
if (check_square(board, i, j)) {
ans++;
}
}
}
cout << ans << endl;
return 0;
}
# マス (i, j) にコマを置くことができるか判定する
def check_square(board, i, j):
for b in board[i]:
# すでに同じ行にコマが置かれていたら、コマを置くことはできない
if b:
return False
for row in board:
# すでに同じ列にコマが置かれていたら、コマを置くことはできない
if row[j]:
return False
return True
board = [[c == '#' for c in input()] for i in range(8)]
ans = 0
# それぞれのマスについて、
for i in range(8):
for j in range(8):
# コマが置けるなら答えを 1 増やす
if check_square(board, i, j):
ans += 1
print(ans)
2. コマごとに取れるマスを計算する
空のマス目を用意し、それぞれのコマについて同じ行のマスと同じ列のマスを塗ることを考えます。 この操作が終わったあと塗られていないマスの個数が答えです。
実装例は以下のようになります。
#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 == '#';
}
}
// 置くことができるマスを求める
array<array<bool, 8>, 8> safe{};
// はじめすべて true で初期化
ranges::fill(safe | views::join, true);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
// コマが置かれていたら、
if (board[i][j] == 1) {
// 同じ行のマスに置くことはできない
for (int k = 0; k < 8; k++) {
safe[i][k] = false;
}
// 同じ列のマスに置くことはできない
for (int k = 0; k < 8; k++) {
safe[k][j] = false;
}
}
}
}
// 置くことができるマスの合計を出力
cout << ranges::count(safe | views::join, true) << endl;
return 0;
}
board = [[c == '#' for c in input()] for i in range(8)]
# 置くことができるマスを求める
# はじめすべて 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 b:
for k in range(8):
# 同じ行のマスに置くことはできない
safe[i][k] = False
# 同じ列のマスに置くことはできない
safe[k][j] = False
# 置くことができるマスの合計を出力
print(sum(+f for row in safe for f in row))
投稿日時:
最終更新: