ABC96 C-Grid Repainting 2

問題概要

• H行W列のマス目で表されるキャンバスがあり、最初、全てのマス目は白色である。
• このキャンバスに黒い絵の具を使って絵を描く時、\(s_{i,j}\) = '#'の時、マス(i, j)を黒色、\(s_{i,j}\) ='.'の時、マス(i, j)を白色にすることがゴールである。
• しかし、黒く塗る時、次のような制約の下で塗らなければいけない
  • 上下左右に隣接する２つのマスを選び両方黒く塗る
  • すでに黒く塗られているマスを選ぶこともでき、この時は黒のまま

ゴールの図形を描くことができるかどうかを判定せよ。

制約

• Hは1以上50以下の整数
• Wは1以上50以下の整数

問題へのリンクはこちら

考えたこと

• 孤立する#が存在しなければ必ずゴールとなる図形を描写できる。ただし、ここでいう孤立とは、#の上下左右が全て.で表されるような状況のことを指す。
• マスの数が50 \(\times\) 50 程度しかないため、全探索で求められる。

#include<bits/stdc++.h>
using namespace std;
// 上下左右を表すための配列
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int HMAX=50;
const int WMAX=50;

int main() {
  int h, w; cin >> h >> w;
  char s[WMAX][HMAX];
  for(int y = 0; y < h; ++y) {
    for(int x = 0; x < w; ++x) {
      cin >> s[x][y];
    }
  }
  for(int y = 0; y < h; ++y) {
    for(int x = 0; x < w; ++x) {
      if(s[x][y] == '#') {
        int cnt = 0;
        for(int i = 0; i < 4; ++i) {
          if(s[x+dx[i]][y+dy[i]] == '#') cnt++;
        }
        if(cnt == 0) {
          cout << "No" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Yes" << endl;

  return 0;
}