Overview

This problem asks you to determine whether all servers (#) placed on an \(N \times M\) grid have an adjacent server count between \(1\) and \(3\) inclusive.

Analysis

Understanding the Problem

First, let’s clarify what “adjacent server count” means.

For a given server, we examine the 4 directions (up, down, left, right) and count the number of rooms containing servers (#).

Concrete Examples:

...
.#.
...

In this case, the central server has an adjacent server count of \(0\) (all four directions are empty rooms). This does not satisfy the condition.

.#.
###
.#.

In this case, the central server has an adjacent server count of \(4\) (servers in all four directions). This also does not satisfy the condition.

.#.
##.
...

In this case: - Top server: adjacent server count = \(1\) (only below) → OK - Bottom-left server: adjacent server count = \(2\) (above and right) → OK - Right server: adjacent server count = \(1\) (only left) → OK

Approach Consideration

This problem can be solved simply by “checking the condition for all servers.”

Since we only need to check 4 adjacent cells for each server, the processing per server is \(O(1)\). Even scanning the entire grid takes \(O(N \times M)\), which is sufficiently fast.

No special algorithm is required; a straightforward brute-force search will solve this.

Algorithm

1. Read the grid
2. For each cell \((i, j)\) in the grid:
   • Skip if the cell is not a server (#)
   • If it is a server, examine the 4 directions (up, down, left, right)
   • For each direction, if it’s within the grid boundaries and is a server, increment the adjacent server count by \(+1\)
3. If the adjacent server count is less than \(1\) or greater than \(3\), immediately output No and terminate
4. If all servers satisfy the condition, output Yes

Direction Representation: Up, down, left, right are represented as \((di, dj)\): - Up: \((-1, 0)\) - Down: \((1, 0)\) - Left: \((0, -1)\) - Right: \((0, 1)\)

Complexity

• Time Complexity: \(O(N \times M)\)
  • We visit each cell of the grid once and check at most 4 directions per cell
• Space Complexity: \(O(N \times M)\)
  • Required to store the grid

Implementation Notes

1. Boundary Checking: When examining adjacent cells, you need to check 0 <= ni < N and 0 <= nj < M to avoid accessing outside the grid boundaries. Servers at edges or corners have only 2-3 adjacent cells.

2. Early Termination: As soon as a server that doesn’t satisfy the condition is found, you can output No and terminate. This shortens processing in cases other than the worst case.

3. Using Direction Vectors: Defining the 4 directions (up, down, left, right) in an array allows for concise loop processing. This reduces mistakes compared to manually writing 4 if statements.

Source Code

def solve():
    N, M = map(int, input().split())
    grid = []
    for _ in range(N):
        grid.append(input().strip())
    
    # Directions: 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 adjacent servers
                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
                
                # If adjacent server count is not between 1 and 3, output No
                if adjacent_count < 1 or adjacent_count > 3:
                    print("No")
                    return
    
    print("Yes")

solve()

---

This editorial was generated by claude4.5opus.