픽셀
면접 대비시간 제한3초메모리 제한512 MB
목표 흑백 격자가 주어질 때, 스위치를 누르면 해당 칸과 상하좌우 이웃 칸의 색이 뒤집힌다. 목표를 만드는 스위치 집합을 찾는다.
문제
야생 동물을 보호하는 방법은 여러 가지다. 그중 하나는 사람들에게 영감을 주는 포스터를 만드는 것이고, 이는 예술가의 일이다. 영감을 받아야 하는 사람 중에는 괴짜들도 있기에, 일부 예술가는 픽셀 아트에 집중한다.
한 예술가가 동물을 흑백으로 묘사하는 픽셀 아트 그림을 준비했다. 이 그림은 K개의 행(위에서 아래로 0부터 K − 1까지)과 L개의 열(왼쪽에서 오른쪽으로 0부터 L − 1까지)로 이루어진 거대한 픽셀 사각형 화면에 표시되어야 한다. 이런 화면에 그림을 표시하는 것이 당신의 일이다.
화면을 초기화하면 흰색 픽셀만 표시된다. 이후 각 픽셀은 스위치로 개별 제어되어야 하며, 픽셀 P의 스위치를 누르면 P의 색이 검은색에서 흰색으로 또는 흰색에서 검은색으로 바뀌어야 한다. 하지만 화면에는 결함이 있다. 픽셀 P의 스위치를 누르면 P와 변을 공유하는 픽셀, 즉 가로 또는 세로로 인접한 픽셀(대각선은 제외)의 색도 바뀐다. 그래도 누를 스위치를 적절히 선택하면 이 결함 있는 화면으로도 받은 그림을 표시할 수 있을지도 모른다.
그림을 표시할 수 있는가? 가능하다면, 어떤 스위치를 눌러야 하는가?
입력
- 첫째 줄에 두 정수 K와 L이 공백으로 구분되어 주어진다.
- 0 ≤ i < K인 모든 i에 대해, i + 2번째 줄에 L개의 기호 “B” 또는 “W”가 공백으로 구분되어 주어진다. j번째 기호(0 ≤ j < L)가 “B”이면 i번째 행과 j번째 열에 표시될 픽셀은 검은색이어야 하고, 그렇지 않으면 흰색 픽셀이어야 한다.
출력
스위치를 눌러 원하는 그림을 표시할 방법이 없으면, “IMPOSSIBLE”이라는 단어 한 줄만 출력해야 한다.
그렇지 않으면 K개의 줄을 출력해야 하며, 각 줄에는 L개의 기호 “A” 또는 “P”가 공백으로 구분되어 있어야 한다.
- 0 ≤ i < K이고 0 ≤ j < L인 모든 i, j에 대해, i + 1번째 줄의 j번째 기호가 “P”이면 i번째 행과 j번째 열의 픽셀에 연결된 스위치를 눌러야 하고, 그렇지 않으면 그 스위치를 누르지 않아야 한다.
제한
- 1 ≤ K × L ≤ 100 000.
힌트
스위치를 누르는 순서는 중요하지 않으며, 같은 스위치를 두 번 누를 필요는 없다. 따라서 해는 누른 스위치의 집합으로 완전히 설명할 수 있다. 해가 여러 개일 수 있다. 즉, 적절한 스위치 집합이 여러 개일 수 있다. 그런 경우에는 그러한 해 중 하나만 출력하면 된다.