概要

与えられたグリッド上のサーバー配置に対し、すべてのサーバーが「隣接するサーバーの数」が \(1\) 以上 \(3\) 以下であるかどうかを判定する問題。

考察

この問題では、各サーバー（#）に対して、上下左右に隣接するセルに何個のサーバーがあるかを数え、それが \(1\) 個以上 \(3\) 個以下であることを確認する必要があります。

素朴な方法としては、すべてのマスを走査し、サーバーがあればその上下左右を調べるというアプローチがあります。これは十分高速であり、特に工夫なしでも時間制限内に動作します。

重要なのは、境界処理を忘れずにすることです。グリッドの端にあるサーバーの場合、上下左右のすべての方向に隣接するマスが存在するとは限りません。そのため、インデックスが有効な範囲内（\(0 \leq ni < N\), \(0 \leq nj < M\)）にあるかを必ず確認する必要があります。

さらに、もし一つでも条件を満たさないサーバーがあれば、その時点で "No" を出力して終了できます。すべてをチェックする必要はありません。

アルゴリズム

1. 入力を読み込み、\(N \times M\) のグリッドを保持する。
2. 各マス \((i, j)\) を走査する：
   • マスがサーバー (#) であれば、上下左右4方向の隣接マスを調べる。
   • 隣接マスがグリッド内にあり、かつサーバーである場合、カウントを増やす。
3. カウントが \(0\) または \(4\) であれば "No" を出力して終了。
4. すべてのサーバーが条件を満たせば "Yes" を出力。

計算量

• 時間計算量: \(O(N \times M)\)
  各マスを一度だけ確認し、各マスに対して最大4方向を調べるため、線形時間で解けます。
• 空間計算量: \(O(N \times M)\)
  グリッド全体を保持するのに必要なメモリ量です。

実装のポイント

• 上下左右の移動は、事前に定義した方向ベクトルを使って簡潔に記述できる。
• インデックスの範囲外アクセスを防ぐために、隣接マスがグリッド内にあるかを必ず確認する。
• 条件を満たさないサーバーが見つかったら即座に "No" を出力してプログラムを終了することで、無駄な計算を省略できる。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    grid = data[2:2+N]
    
    # Directions for adjacent cells (up, down, left, right)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for i in range(N):
        for j in range(M):
            if grid[i][j] == '#':
                count = 0
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < N and 0 <= nj < M and grid[ni][nj] == '#':
                        count += 1
                if not (1 <= count <= 3):
                    print("No")
                    return
    print("Yes")

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。