흰색으로 만들기
시간 제한1초메모리 제한512 MB
N×M 흑백 격자에서 각 칸마다 세 가지 국소 반전 동작 중 하나를 골라 모든 칸을 흰색으로 만들거나, 불가능하면 -1을 출력한다.
문제
N행 M열 격자판의 각 격자가 흰색 또는 검은색으로 칠해져 있다. 각 칸에 대해 다음의 3가지 중 1가지 행동을 취할 수 있다.
- 아무 변화도 주지 않는다.
- 선택한 칸과 인접한 모든 칸의 색을 반전시킨다. 단, 선택한 칸은 반전시키지 않는다.
- 선택한 칸 및 그 칸과 인접한 모든 칸의 색을 반전시킨다.
모든 칸을 흰색으로 만드는 방법을 구하여라.
입력
첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 2,000)
다음 줄부터 N개의 줄에 걸쳐 각 행의 상태를 나타내는 길이 M의 문자열이 주어진다. 모든 문자열은 'B'와 'W'로 이루어져 있다. i번째 줄, j번째 문자가 'B'일 경우 해당 칸이 검은색이며 'W'일 경우 해당 칸이 흰색임을 의미한다.
출력
모든 칸을 흰색으로 만드는 것이 불가능하다면 첫 줄에 -1을 출력한다.
가능하다면 첫 줄에 1을 출력하고, 다음 줄부터 N개의 줄에 걸쳐 M개의 수를 공백 없이 출력한다.
i번째 줄의 j번째 수는 i번째 줄, j번째 칸에 취한 행동을 나타낸다. 1은 아무런 변화를 주지 않은 것, 2는 인접한 모든 칸을 반전시킨 것, 3은 그 칸 및 인접한 모든 칸을 반전시킨 것을 의미한다.
가능한 답이 여럿이라면 그 중 아무것이나 출력한다.