Overview

For each cell that is # (a server), this problem asks you to determine via brute force whether the number of adjacent # cells (up, down, left, right) falls within the range \(1 \sim 3\) (i.e., it is neither \(0\) nor \(4\)).

Analysis

Each server (#) has at most 4 adjacent cells in the up, down, left, and right directions. Therefore, it suffices to count “the number of # among the 4 adjacent cells” for each # and check whether this violates the condition.

• Adjacent server count is \(0\): isolated (not OK)
• Adjacent server count is \(4\): surrounded by servers on all four sides, overcrowded (not OK)
• Otherwise (\(1, 2, 3\)): OK

A naive implementation requires an if-statement for bounds checking every time to avoid “out-of-grid access” at the edges (top row, bottom row, leftmost column, rightmost column), which tends to make the code cumbersome.
By creating a “sentinel (padding) grid” where the surroundings are filled with . by one cell, you can always safely reference i-1, i+1, j-1, j+1, reducing the chance of implementation bugs (WA).

Algorithm

1. Create a grid with one extra layer of . added on all four sides of the input grid (size becomes \((N+2)\times(M+2)\)).
2. Scan the original range (\(1 \le i \le N, 1 \le j \le M\)).
3. When cell \((i,j)\) is #, count how many of the 4 adjacent cells (up, down, left, right) are #:
   • grid[i-1][j], grid[i+1][j], grid[i][j-1], grid[i][j+1]
4. If the count cnt is \(0\) or \(4\), immediately output No and terminate.
5. If no violations are found by the end, output Yes.

(Example) If the surroundings of a # are like .#.# with only 2 directions being #, then cnt=2 which is OK. If all four directions are #, then cnt=4 which is NG.

Complexity

• Time complexity: \(O(NM)\) (each cell is visited once with a constant number of checks)
• Space complexity: \(O(NM)\) (to store the grid with padding)

Implementation Tips

• Sentinel (padding): By adding '.'*(M+2) to the top and bottom, and prepending/appending '.' to each row on the left and right, boundary checks become unnecessary.

• In Python, True/False can be added as 1/0, so you can count concisely using the form:
  cnt = (a=='#') + (b=='#') + ...

• The condition is “\(1 \le cnt \le 3\)”, but in implementation, using the equivalent check “reject if cnt==0 or cnt==4” makes the branching simpler.

  Source Code

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

This editorial was generated by gpt-5.2-high.