AtCoder ABC 241 C - Connect 6 (2Q, 茶色, 300 点)

実装問題！

• 問題へのリンク

問題概要

のグリッドがあって、各マスは白色または黒色に塗られている。今、「白色のマスを選んで黒色に塗る」という操作を高々 2 回まで実施できる。

操作後に、縦・横・斜めのいずれかに連続して 6 個のマスが黒色になるようにすることが可能かどうかを判定せよ。

制約

• 

考えたこと

まず愚直に「2 個のマスを全探索して判定する」という方針が思い浮かぶかもしれない。しかし、マスの個数自体が 個あり、2 個のマスを選ぶ方法は 通りある。とても間に合わない。

そこで、方針転換して、次の方針をとろう。

---

与えられたグリッドの縦 6 マス、横 6 マス、斜め 6 マスであって、黒色マスが 4 個以上含まれるものがあるかどうかを判定する。

---

具体的な解法としては、各マス から出発して、

• 下方向に 6 マス分を見る
• 右方向に 6 マス分を見る
• 右下斜め方向に 6 マス分を見る
• 左下斜め方向に 6 マス分を見る

をやればよい。これならば、計算量は となる。

コード

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

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    
    bool res = false;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            // (i, j) から縦に 6 個の中に '#' が 4 個以上あるか
            if (i + 5 < N) {
                int num = 0;
                for (int d = 0; d < 6; ++d) {
                    if (S[i + d][j] == '#') ++num;
                }
                if (num >= 4) res = true;
            }
            
            // (i, j) から横に 6 個の中に '#' が 4 個以上あるか
            if (j + 5 < N) {
                int num = 0;
                for (int d = 0; d < 6; ++d) {
                    if (S[i][j + d] == '#') ++num;
                }
                if (num >= 4) res = true;
            }
            
            // (i, j) から右斜めに 6 個の中に '#' が 4 個以上あるか
            if (i + 5 < N && j + 5 < N) {
                int num = 0;
                for (int d = 0; d < 6; ++d) {
                    if (S[i + d][j + d] == '#') ++num;
                }
                if (num >= 4) res = true;
            }
            
            // (i, j) から左斜めに 6 個の中に '#' が 4 個以上あるか
            if (i + 5 < N && j - 5 >= 0) {
                int num = 0;
                for (int d = 0; d < 6; ++d) {
                    if (S[i + d][j - d] == '#') ++num;
                }
                if (num >= 4) res = true;
            }
        }
    }
    
    cout << (res ? "Yes" : "No") << endl;
}