Overview

Given servers (#) placed on an \(N \times M\) grid, determine whether all servers satisfy the condition that “the number of adjacent servers in the four cardinal directions (up, down, left, right) is at least 1 and at most 3.”

Analysis

This problem can be solved by examining each cell of the grid in order.

1. Organizing the conditions:

   • Focus only on cells that contain a server (#).
   • Check the 4 directions (up, down, left, right) from that cell and count how many # cells there are.
   • If the count is \(0\) (isolated) or \(4\) (overloaded), then there is a security policy violation (No) at that point.
   • If all servers have between \(1\) and \(3\) adjacent servers, the answer is Yes.

2. Checking the constraints:

   • Since \(N\) and \(M\) are at most 1000, the total number of cells is at most \(1,000,000\) (1 million).
   • Checking 4 directions for each cell takes constant time, so a single scan of the grid is sufficient.

3. Boundary handling:

   • When checking servers at the edges of the grid (such as the first row or first column), care must be taken to avoid referencing outside the grid and causing errors.

Algorithm

1. Read the grid state as a 2-dimensional array (or a list of strings).
2. Using a nested loop, iterate over rows \(r\) (from \(0\) to \(N-1\)) and columns \(c\) (from \(0\) to \(M-1\)).
3. If grid[r][c] is #:
   • Initialize a variable count to 0.
   • Check the 4 adjacent cells (up, down, left, right), and if a cell is within bounds and is #, increment count by 1.
   • If count is not one of \(1, 2, 3\) (i.e., count < 1 or count > 3), immediately output No and terminate.
4. After checking all cells, output Yes and terminate.

Complexity

• Time complexity: \(O(N \times M)\)
  • We scan all cells of the grid once and check at most 4 directions for each cell, so the processing time is proportional to the number of cells.
• Space complexity: \(O(N \times M)\)
  • This is the memory required to store the input grid information.

Implementation Notes

• Efficient input: In Python, using sys.stdin.read().split() allows fast reading of large inputs.

• Early return: By outputting No and terminating the moment any server that violates the condition is found, unnecessary computation is avoided.

• Boundary checks: By including conditional expressions such as if r > 0, if r < n - 1, if c > 0, if c < m - 1, we prevent IndexError from occurring due to accessing outside the grid.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.