実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 50

問題概要

縦8マス、横8マスからなるマス目があり、上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と呼ぶ。それぞれのマスは、空マスであるかコマが置かれているかのどちらかで、マスの状態は長さ8の文字列からなる長さ8の列 $(S_1, S_2, \cdots, S_8)$ で表され、マス $(i,j)$ は、 $S_i_j$ が.のとき空マスで、#のときコマが置かれている。

これから、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置くことを考える。マス $(i, j)$ に置かれているコマは、次のどちらかの条件を満たすコマを取ることができる。

$i$ 行目のマスに置かれている
$j$ 列目のマスに置かれている

このとき、自分のコマを置くことができるマスがいくつあるか求めよ。

制約

問題文の通り。

考察

考えるべきマスが64マスしかないので、全探索を考える。

具体的には、自分のコマを置くことができるマスにフラグを立てておき、各コマについて同じ行・列のフラグを折っていく。最終的に立っているフラグの数を出力すればよい。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    vector<string> field(8);
    rep(i, 0, 8) cin >> field[i];

    vector<vector<bool>> check(8, vector<bool>(8, true));
    rep(i, 0, 8) rep(j, 0, 8)
    {
        if (field[i][j] == '#')
        {
            rep(k, 0, 8) check[k][j] = false;
            rep(k, 0, 8) check[i][k] = false;
        }
    }

    int ans = 0;
    rep(i, 0, 8) rep(j, 0, 8) if (check[i][j]) ans++;

    cout << ans << endl;
}