Official

C - Avoid Rook Attack Editorial by MMNMM


この問題は、次の \(2\) つの方針で解くことができます。

  1. それぞれのマスについて、どのコマからも取られないか判定する
  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))

posted:
last update: