Mosaic

시간 제한2초메모리 제한1024 MB

요약
3x3 검은 칸 개수를 담은 R x C 행렬이 주어질 때 이를 만들어 내는 흑백 그림을 하나 복원하거나, 존재하지 않으면 0을 출력한다.
난이도

어려움10점 중 8점

유형
그리디, 구현, 완전 탐색, 행렬
정답자
아직 제출이 없습니다

문제

Mosa is an abstract artist. All of her paintings can be represented as a rectangular grid of black and white unit squares.

Lina is an art collector. His favorite hobby is counting black squares in Mosa’s paintings. One day, he took one of her paintings of RR rows and CC columns, and recorded an RR-by-CC matrix, such that the number at row rr, column cc in the matrix equals the number of black unit squares in the 33-by-33 square region centered at the square at row rr, column cc.

Unfortunately, the very next day Lina found that the artwork is missing! All he has now is the matrix of numbers. Can you help Lina recover Mosa’s painting?

Lina might have made a mistake while writing down the numbers, so it is possible that such a painting does not exist for a given matrix.

입력

The first line contains two integers RR and CC separated by a space.

The next RR lines contain CC nonnegative integers each, also separated by a space. Each number does not exceed 99.

출력

If such a painting exists, output 1 on the first line, and the painting over the next RR lines. Each line should be a string of length CC, consisting of characters B (for Black) and W (for White). If multiple paintings satisfy the condition, output any one of them.

If such a painting does not exist, output 0 on the first line.

제한

  • 1≤R,C≤1,0001\le R,C\le 1\\, 000

예제2

  1. 예제 1

    입력
    5 5
4 6 6 6 4
6 8 8 8 6
6 8 8 8 6
6 8 8 8 6
4 6 6 6 4
    예상 출력
    1
BBBBB
BBBBB
BBWBB
BBBBB
BBBBB

  2. 예제 2

    입력
    4 4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
    예상 출력
    0