Overview

Given a server placement on a grid, determine whether every server has a number of “adjacent servers” that is at least \(1\) and at most \(3\).

Analysis

In this problem, for each server (#), we need to count how many servers are in the cells adjacent to it (up, down, left, right), and verify that this count is at least \(1\) and at most \(3\).

A straightforward approach is to scan all cells, and for each server, check its four neighboring cells (up, down, left, right). This is sufficiently fast and runs within the time limit without any special optimizations.

An important point is to not forget boundary handling. For servers located at the edge of the grid, not all four directions necessarily have adjacent cells. Therefore, we must always verify that the indices are within valid range (\(0 \leq ni < N\), \(0 \leq nj < M\)).

Furthermore, if even a single server fails to satisfy the condition, we can output "No" at that point and terminate. There is no need to check all servers.

Algorithm

1. Read the input and store the \(N \times M\) grid.
2. Scan each cell \((i, j)\):
   • If the cell is a server (#), examine the adjacent cells in all 4 directions (up, down, left, right).
   • If an adjacent cell is within the grid and is also a server, increment the count.
3. If the count is \(0\) or \(4\), output "No" and terminate.
4. If all servers satisfy the condition, output "Yes".

Complexity

• Time complexity: \(O(N \times M)\)
  Each cell is checked exactly once, and for each cell we examine at most 4 directions, so the problem can be solved in linear time.
• Space complexity: \(O(N \times M)\)
  This is the memory required to store the entire grid.

Implementation Notes

• Movement in the four directions can be written concisely using pre-defined direction vectors.

• To prevent out-of-bounds access, always verify that adjacent cells are within the grid.

• If a server that does not satisfy the condition is found, immediately output "No" and terminate the program to avoid unnecessary computation.

  Source Code

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

This editorial was generated by qwen3-coder-480b.