概要

\(N \times M\) のグリッド上に配置されたサーバー（#）について、すべてのサーバーが「上下左右に隣接するサーバー数が 1 つ以上 3 つ以下」という条件を満たしているかを判定する問題です。

考察

この問題は、グリッドの各マスを順番に確認していくことで解くことができます。

1. 条件の整理:

   • サーバーがあるマス（#）のみに注目します。
   • そのマスの「上・下・左・右」の 4 方向を確認し、# がいくつあるか数えます。
   • カウントした数が \(0\)（孤立）または \(4\)（過負荷）であれば、その時点でセキュリティポリシー違反（No）となります。
   • すべてのサーバーが \(1 \sim 3\) 個の隣接サーバーを持っていれば Yes となります。

2. 制約の確認:

   • \(N\) と \(M\) は最大 1000 なので、全マス数は最大 \(1,000,000\)（100万）です。
   • 各マスに対して 4 方向をチェックする操作は定数時間で行えるため、グリッドを 1 回走査するだけで十分間に合います。

3. 境界の処理:

   • グリッドの端（1行目や1列目など）にあるサーバーをチェックする際、グリッドの外側を参照してエラーにならないよう注意が必要です。

アルゴリズム

1. グリッドの状態を 2 次元配列（または文字列のリスト）として読み込みます。
2. 二重ループを用いて、行 \(r\) (\(0\) から \(N-1\))、列 \(c\) (\(0\) から \(M-1\)) を走査します。
3. grid[r][c] が # である場合：
   • 変数 count を 0 で初期化します。
   • 上下左右の 4 マスを確認し、範囲内かつ # であれば count を 1 増やします。
   • count が \(1, 2, 3\) のいずれでもない（count < 1 または count > 3）なら、即座に No を出力して終了します。
4. すべてのマスを確認し終えたら、Yes を出力して終了します。

計算量

• 時間計算量: \(O(N \times M)\)
  • グリッドの全マスを 1 回ずつ走査し、各マスで最大 4 方向を確認するため、マス数に比例した時間で処理が終わります。
• 空間計算量: \(O(N \times M)\)
  • 入力されたグリッドの情報を保持するために必要なメモリ量です。

実装のポイント

• 効率的な入力: Python では sys.stdin.read().split() を使うことで、大きな入力も高速に読み込むことができます。

• 早期リターン: 1 つでも条件を満たさないサーバーが見つかった瞬間に No を出力して終了することで、無駄な計算を省いています。

• 境界チェック: if r > 0, if r < n - 1, if c > 0, if c < m - 1 といった条件式を入れることで、グリッドの外側にアクセスして IndexError が発生するのを防いでいます。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、空白（スペース、タブ、改行）で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # グリッドの縦の長さ N と横の長さ M を取得
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 各行の状態を取得（N行分）
    grid = input_data[2:2+n]
    
    # 各部屋を走査してセキュリティポリシーを確認する
    for r in range(n):
        row = grid[r]
        # 上下の行をあらかじめ取得して計算を最適化する
        prev_row = grid[r-1] if r > 0 else None
        next_row = grid[r+1] if r < n - 1 else None
        
        for c in range(m):
            # サーバーが設置されている部屋（'#'）のみをチェック
            if row[c] == '#':
                count = 0
                # 上にサーバーがあるか
                if prev_row and prev_row[c] == '#':
                    count += 1
                # 下にサーバーがあるか
                if next_row and next_row[c] == '#':
                    count += 1
                # 左にサーバーがあるか
                if c > 0 and row[c-1] == '#':
                    count += 1
                # 右にサーバーがあるか
                if c < m - 1 and row[c+1] == '#':
                    count += 1
                
                # 隣接サーバー数が 1 以上 3 以下でない場合はポリシー違反
                if not (1 <= count <= 3):
                    print("No")
                    return
    
    # すべてのサーバーが条件を満たしている場合
    print("Yes")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。