【競プロ】1日1AC : ABC96 C問題

今日はやる気があるので2記事目です。問題はこちら。

Difficultyは369（灰）です。
（AtCoder Problemsより）

1つ前の問題の類題なので、余裕があればそっちも解いてみてください。（難易度は同じくらいです）

【競プロ】1日1AC : ABC75 B問題

2020年3月30日

提出コードと考え方

「#」が2つ以上隣接している部分には色を塗れます。そうではない時、つまりある「#」の上下左右が全て「.」の場合は色が塗れません。
よって、全ての「#」について調べて、後者の条件を満たすものがあれば”No”、なければ”Yes” と出力すればいいです。

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

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<char>> data(h+2,vector<char>(w+2,'.'));
    for(int i = 1;i <= h;i++){
        for(int j = 1;j <= w;j++){
            cin >> data[i][j];
        }
    }
    
    bool isYes = true;
    for(int i = 1;i <=h;i++){
        for(int j = 1;j <= w;j++){
            if(data[i][j] == '.') continue;
            bool isExist = false;
            for(int k = 0;k < 4;k++){
                if(data[i+dx[k]][j+dy[k]] == '#') isExist = true;
            }
            if(!isExist){
                isYes = false;
                break;
            }
        }
        if(!isYes) break;
    }
    if(isYes) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

1つ前の記事でも同じことをしましたが、与えられたキャンバスについてそのまま調べると、キャンバス端のマス目が範囲外を調べないように処理を書く必要があります。しかし、予め周りを「.」で埋めておくと全てのマスが同じ処理で済みます。

また、これも前の記事で書きましたが、隣を調べるときは動く差分の組 \( (dx,dy)\) を用意しておくと楽です。