概要

#（サーバー）の各マスについて、上下左右に隣接する # の個数が \(1 \sim 3\) に収まっているか（つまり \(0\) や \(4\) になっていないか）を全探索で判定する問題です。

考察

各サーバー（#）は上下左右の最大 4 方向にしか隣接しません。したがって、各 # について「隣接 4 マスのうち # の個数」を数え、これが条件に違反していないかを調べれば十分です。

• 隣接サーバー数が \(0\)：孤立（ダメ）
• 隣接サーバー数が \(4\)：四方がサーバーで過密（ダメ）
• それ以外（\(1,2,3\)）：OK

素朴に実装すると、端（最上段・最下段・最左列・最右列）では「グリッド外参照」を避けるために毎回 if 文で範囲チェックが必要になり、コードが煩雑になりがちです。
そこで 周囲を . で1マス分埋めた“番兵（パディング）付きグリッド” を作ると、常に安全に i-1, i+1, j-1, j+1 を参照でき、実装ミス（WA）の原因を減らせます。

アルゴリズム

1. 入力のグリッドの外側に、上下左右 1 マス分 . を追加したグリッドを作る（サイズは \((N+2)\times(M+2)\)）。
2. 元の範囲（\(1 \le i \le N, 1 \le j \le M\)）を走査する。
3. マス \((i,j)\) が # のとき、上下左右の 4 マスが # かどうかを数える：
   • grid[i-1][j], grid[i+1][j], grid[i][j-1], grid[i][j+1]
4. その個数 cnt が \(0\) または \(4\) なら即座に No を出力して終了。
5. 最後まで違反がなければ Yes。

（例）ある # の周りが .#.# のように 2 方向だけ # なら cnt=2 でOK、上下左右すべて # なら cnt=4 でNGです。

計算量

• 時間計算量: \(O(NM)\)（各マスを1回見て、定数回のチェックをするだけ）
• 空間計算量: \(O(NM)\)（パディング込みのグリッドを保持）

実装のポイント

• 番兵（パディング）：上下に '.'*(M+2) を追加し、各行にも左右に '.' を付けると、境界判定が不要になります。

• Python では True/False が 1/0 として加算できるので、
  cnt = (a=='#') + (b=='#') + ... の形で簡潔に数えられます。

• 条件は「\(1 \le cnt \le 3\)」ですが、実装では同値な「cnt==0 または cnt==4 を弾く」とすると分岐が単純になります。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    grid = ['.' * (M + 2)]
    for _ in range(N):
        s = input().strip()
        grid.append('.' + s + '.')
    grid.append('.' * (M + 2))

    for i in range(1, N + 1):
        row = grid[i]
        for j in range(1, M + 1):
            if row[j] == '#':
                cnt = (grid[i-1][j] == '#') + (grid[i+1][j] == '#') + (row[j-1] == '#') + (row[j+1] == '#')
                if cnt == 0 or cnt == 4:
                    print("No")
                    return
    print("Yes")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。