概要

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

考察

問題の理解

まず、「隣接サーバー数」とは何かを整理しましょう。

あるサーバーに対して、上下左右の4方向を調べ、その中でサーバー（#）が存在する部屋の数を数えます。

具体例:

...
.#.
...

この場合、中央のサーバーの隣接サーバー数は \(0\) です（上下左右すべてが空き部屋）。これは条件を満たしません。

.#.
###
.#.

この場合、中央のサーバーの隣接サーバー数は \(4\) です（上下左右すべてにサーバー）。これも条件を満たしません。

.#.
##.
...

この場合： - 上のサーバー：隣接サーバー数 = \(1\)（下のみ）→ OK - 左下のサーバー：隣接サーバー数 = \(2\)（上と右）→ OK - 右のサーバー：隣接サーバー数 = \(1\)（左のみ）→ OK

アプローチの検討

この問題は単純に「すべてのサーバーについて条件をチェックする」だけで解けます。

各サーバーについて上下左右の4マスを確認するだけなので、1つのサーバーあたりの処理は \(O(1)\) です。グリッド全体を走査しても \(O(N \times M)\) で十分高速です。

特別なアルゴリズムは不要で、愚直な全探索で解けます。

アルゴリズム

1. グリッドを読み込む
2. グリッドの各マス \((i, j)\) について以下を行う：
   • そのマスがサーバー（#）でなければスキップ
   • サーバーであれば、上下左右の4方向を調べる
   • 各方向について、グリッドの範囲内かつサーバーであれば、隣接サーバー数を \(+1\)
3. 隣接サーバー数が \(1\) 未満または \(3\) より大きければ、即座に No を出力して終了
4. すべてのサーバーが条件を満たしていれば Yes を出力

方向の表現: 上下左右は \((di, dj)\) の形で表現します： - 上: \((-1, 0)\) - 下: \((1, 0)\) - 左: \((0, -1)\) - 右: \((0, 1)\)

計算量

• 時間計算量: \(O(N \times M)\)
  • グリッドの各マスを1回ずつ訪問し、各マスで最大4方向を確認します
• 空間計算量: \(O(N \times M)\)
  • グリッドを格納するために必要です

実装のポイント

1. 境界チェック: 隣接マスを調べる際、グリッドの範囲外を参照しないように 0 <= ni < N と 0 <= nj < M のチェックが必要です。特に端や角にあるサーバーでは、隣接マスが2〜3個しか存在しません。

2. 早期終了: 条件を満たさないサーバーが1つでも見つかった時点で No を出力して終了できます。これにより、最悪ケース以外では処理を短縮できます。

3. 方向ベクトルの活用: 上下左右の4方向を配列で定義しておくと、ループで簡潔に処理できます。手動で4つの if 文を書くよりもミスが減ります。

   ソースコード

def solve():
    N, M = map(int, input().split())
    grid = []
    for _ in range(N):
        grid.append(input().strip())
    
    # 上下左右の方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for i in range(N):
        for j in range(M):
            if grid[i][j] == '#':
                # 隣接サーバー数をカウント
                adjacent_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] == '#':
                        adjacent_count += 1
                
                # 隣接サーバー数が1以上3以下でなければNo
                if adjacent_count < 1 or adjacent_count > 3:
                    print("No")
                    return
    
    print("Yes")

solve()

---

この解説は claude4.5opus によって生成されました。