Atcoder解いてみた　ABC 096 C - Grid Repainting 2

# ABC 096 C - Grid Repainting 2
問題は[こちら](https://atcoder.jp/contests/abc096/tasks/abc096_c)  

## 最初の回答

### 方針
0<=y<H, 0<=x<W の範囲で探索し、隣接する上下のマスに#が1だったらただちにNoを表示する。 
#が1だったらただちにNoを表示する理由は、塗らなくてもOKだが、塗るときは2マスなため。  

### コード
```C++
#include <iostream>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int H;
    int W;
    string canvas[50]; // 縦に50, 横に50文字

    cin >> H;
    cin >> W;

    for (int i = 0; i < H; i++) {
        cin >> canvas[i];
    }
    // 0~H-1, 0~W-1のインデックスとする
    //上下左右に隣接するマスを塗る
    // 1<=y<H-1, 1<=x<W-1 の範囲で探索
    // いや、0<=y<H, 0<=x<W の範囲で探索
    // 探索していき、上下左右の隣接領域に、#が1つしかなかったらダメ

    for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {

            // #のマスのカウント
            int blackCount = 0;

            // 上下左右のみ!!

            // 上下
            for (int yc = y - 1; yc <= y + 1; yc++) {
                if (0 <= yc && yc < H) {
                    string canvasH = canvas[yc];
                    char word = canvasH[x];

                    if (word == '#') blackCount++;
                }
            }
            // 左右
            for (int xc = x - 1; xc <= x + 1; xc++) {
                if (0 <= xc && xc < W) {
                    string canvasH = canvas[y];
                    char word = canvasH[xc];

                    if (word == '#') blackCount++;
                }
            }

            // 中心が#だった場合の重複カウントを考慮
            string canvasH = canvas[y];
            char word = canvasH[x];
            if (word == '#') blackCount--;

            // 黒で塗れるマスが1個だったら(塗らないときは塗らない、塗るときは2マス塗る)
            // 黒く塗れるマスが1個でも、Yesの場合がある、、、
            if (blackCount == 1) {
                std::cout << "No" << std::endl;
                return 0; // この時点でreturnさせる
            }
        }
    }

    // 途中でreturnされなかったらOK
    std::cout << "Yes" << std::endl;

    return 0;
}
```

しかし、三番目のサンプルに対応できず、ヒントを見た  


## 次の回答

### 方針
#のマスに注目し、隣接する上下左右のマスを探索し、#のマスが1つしかなかったらNoにするだけで良かった  

### コード
```C++
#include <iostream>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int H;
    int W;
    string canvas[51]; // 縦に50, 横に50文字

    cin >> H;
    cin >> W;

    for (int i = 0; i < H; i++) {
        cin >> canvas[i];
    }
    // 0~H-1, 0~W-1のインデックスとする
    //上下左右に隣接するマスを塗る
    // 1<=y<H-1, 1<=x<W-1 の範囲で探索
    // いや、0<=y<H, 0<=x<W の範囲で探索
    // 探索していき、上下左右の隣接領域に、#が1つしかなかったらダメ

    // #のマスのみに、注目し、上下左右で探索すればよい!


    for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
            // #のマスのカウンタ
            int blackCount = 0;

            string canvasH = canvas[y];
            char word = canvasH[x];
            if (word == '#') {
                // 上下
                for (int yc = y - 1; yc <= y + 1; yc++) {
                    if (0 <= yc && yc < H) {
                        string canvasH = canvas[yc];
                        char word = canvasH[x];

                        if (word == '#') blackCount++;
                    }
                }
                // 左右
                for (int xc = x - 1; xc <= x + 1; xc++) {
                    if (0 <= xc && xc < W) {
                        string canvasH = canvas[y];
                        char word = canvasH[xc];

                        if (word == '#') blackCount++;
                    }
                }

                blackCount--; // 重複カウントを考慮
                // 黒で塗れるマスが1個だったら(注目座標のみの場合)
                if (blackCount == 1) {
                    std::cout << "No" << std::endl;
                    return 0; // この時点でreturnさせる
                }
            }
        }
    }

    // 途中でreturnされなかったらOK
    std::cout << "Yes" << std::endl;

    return 0;
}

```