【AtCoder】ABC 390 C - Paint to make a rectangle | 緑コーダーが解くAtCoder

配点: 300 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 247

問題概要
制約
考察
実装例
コメント

問題概要

$H \times W$ のマス目が与えられる。以下、上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ で表す。

マス目の状態は $H$ 個の長さ $W$ の文字列 $S_1,S_2, \cdots, S_H$ によって以下のように表される。

$S_{i, j} =$ # : マス $(i,j)$ は黒く塗られている。
$S_{i, j} =$ . : マス $(i,j)$ は白く塗られている。
$S_{i, j} =$ ? : マス $(i,j)$ はまだ塗られていない。

ここで、まだ塗られていないマスをそれぞれ白または黒で塗ることで、黒マス全体が長方形をなすようにしたい。より具体的には、ある4つの整数の組 $(a,b,c,d) \: (1\leq a\leq b\leq H, \: 1\leq c\leq d\leq W)$ が存在して、次が成り立つようにしたい。

マス $(i,j) \: (1\leq i\leq H, \: 1\leq j\leq W)$ は、 $a\leq i\leq b$ かつ $c\leq j\leq d$ を満たすとき、黒く塗られている。そうでないとき、白く塗られている。

そのようなことが可能か判定せよ。

制約

$H, W$ は整数で、 $1\leq H,W\leq 1000$ を満たす。
黒く塗られたマスが1つ以上存在する。

考察

黒いマスがどの領域にあるかを調べ(領域 $D$ とする)、 $D$ 内を黒く塗って長方形を作ることを考える。

まず、 $D$ 内の左上、左下、右上、右下のマスを求める必要があるわけだが、これは $k$ 個の黒いマスが $(i_1, j_1), (i_2, j_2), \cdots, (i_k, j_k)$ であるとき、

$\min_i = \underset{1 \leq t \leq k}{\min} i_t$
$\max_i = \underset{1 \leq t \leq k}{\max} i_t$
$\min_j = \underset{1 \leq t \leq k}{\min} j_t$
$\max_j = \underset{1 \leq t \leq k}{\max} j_t$

と定義すれば、それぞれのマスは

左上 : $(\min_i, \min_j)$
左下 : $(\max_i, \min_j)$
右上 : $(\min_i, \max_j)$
右下 : $(\max_i, \max_j)$

と書ける。

この4マスで囲まれる領域 $D$ の中に、白いマスが1個でもあったら $D$ 内で黒い長方形を作ることはできない。逆にそうでない場合は、?のマスを黒く塗ることで黒い長方形を作ることができる。

実装例

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

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

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    rep(i, 0, H) cin >> S[i];

    int min_i = H, max_i = -1, min_j = W, max_j = -1;
    rep(i, 0, H) rep(j, 0, W)
    {
        if (S[i][j] == '#')
        {
            chmin(min_i, i);
            chmax(max_i, i);
            chmin(min_j, j);
            chmax(max_j, j);
        }
    }

    rep(i, 0, H) rep(j, 0, W)
    {
        if ((min_i <= i && i <= max_i) && (min_j <= j && j <= max_j))
        {
            if (S[i][j] == '.')
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}