Official

B - Looped Rope Editorial by en_translator


To solve this problem, it is sufficient to check if every cell satisfies at least one of the following conditions:

  • The cell is painted white.
  • Among the four adjacent cells, exactly two or four of them are painted black.

If any cell violates both of them, the answer is No; if none of them does, the answer is Yes.

This process can be implemented relatively easily using sentinels.

A sentinel is a special value stored in an array or a grid, when we perform a process against it. A sentinel is used in order to reduce the conditional branches in the process. For example, if there are passable cells and obstacles (non-passable cells) in grid and you are forbidden to go outside the grid, instead of writing two conditional branches checking “not advancing into an obstacle” and “not advancing outside the grid,” we can place obstacle cells to the boundary of the grid so that we only need to implement the former.

In our problem, we may place white cells outside the given grid to avoid implementing a check whether there is a cell in each of the four directions.

The following is sample code.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    
    vector field(H + 2, string(W + 2, '.')); // Prepare a grid with one additional row and column than the original size, all painted white

    for (int i = 1; i <= H; ++i) {
        string S;
        cin >> S;
        field[i] = '.' + S + '.'; // Add white cells to both ends of the input
    }

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) { // For every cell
            int black_count = 0; // Counter for black cells around
            if (field[i - 1][j] == '#')
                ++black_count;
            if (field[i][j - 1] == '#')
                ++black_count;
            if (field[i][j + 1] == '#')
                ++black_count;
            if (field[i + 1][j] == '#')
                ++black_count;

            if (field[i][j] == '#' && black_count != 2 && black_count != 4) {
                // Print No and terminate once a violating cell was found
                cout << "No" << endl;
                return 0;
            }
        }
    }

    // All cells satisfies the condition; print Yes and terminate
    cout << "Yes" << endl;
    return 0;
}
H, W = map(int, input().split())

# Prepare a grid with one additional row and column than the original size, all painted white
field = ['.' * (W + 2)] + ['.' + input() + '.' for i in range(H)] + ['.' * (W + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        black_count = 0 # Counter for black cells around
        if field[i - 1][j] == '#':
            black_count += 1
        if field[i][j - 1] == '#':
            black_count += 1
        if field[i + 1][j] == '#':
            black_count += 1
        if field[i][j + 1] == '#':
            black_count += 1
        
        if field[i][j] == '#' and black_count != 2 and black_count != 4:
            # Print No and terminate once a violating cell was found
            print('No')
            exit(0)

# All cells satisfies the condition; print Yes and terminate
print('Yes')

posted:
last update: