はまやんはまやんはまやん

hamayanhamayan's blog

休憩スペース (Refreshment Area) [第16回日本情報オリンピック 予選(オンライン) C]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_c

解説

https://atcoder.jp/contests/joi2017yo/submissions/8139896

重複なく数えるために、かぶらないような特徴を見つけることが大切である。
今回で言えば、休憩スペースの左上端とする座標について考え、そこを全探索する。
全探索した座標から右にDマス分に機材がなければ、そこに設けることができる。
座標の全探索で既に104通りくらいあり、右にマスを見ていってD個分空白になっていれば、答えとしてカウントする。
同様に下に見た場合も考えて、答えについて和を取ると答え。

int H, W, D;
string B[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> D;
    rep(y, 0, H) cin >> B[y];

    int ans = 0;

    // 右
    rep(y, 0, H) rep(x, 0, W - D + 1) {
        int cnt = 0;
        rep(xx, x, x + D) if (B[y][xx] == '.') cnt++;
        if (cnt == D) ans++;
    }

    // 下
    rep(x, 0, W) rep(y, 0, H - D + 1) {
        int cnt = 0;
        rep(yy, y, y + D) if (B[yy][x] == '.') cnt++;
        if (cnt == D) ans++;
    }

    cout << ans << endl;
}