시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 256 MB 6 2 (33%) 1
문제
상상 속의 세계에는 거대한 직사각형 모양의 섬이 있다. 섬의 세로, 가로 길이는 $R, C$ 마일이며 $R \times C$짜리 격자로 구역이 구분되어있다. 몇몇 구역들에는 아무도 살지 않고 나머지는 엘프, 인간, 드워프, 호빗 들의 마을로 이루어져 있다. 한 구역에는 최대 한 개의 마을이 있을 수 있고 맞닿아있는 마을들을 이웃이라고 부른다. 최근 마을들은 거대한 악의 위협을 받게 되었다. 불안을 해소하기 위해 각 마을은 그의 이웃들 중 일부와 군사 동맹을 맺기로 했다. 동맹은 두 인접한 마을 간에 형성되며 상호 간에 대칭적이다. 마을에 어떤 종족이 살고 있는지에 따라, 거주자들이 안심하기 위해서는 아래와 같은 조건의 동맹이 형성되어야 한다. ``` 엘프들은 자신감이 있으므로 정확하게 하나의 이웃과 동맹을 맺고자 한다. 인간들은 정확하게 두 개의 이웃과 동맹을 맺고자 한다. 그리고 두 개의 마주 보는 변이 노출된 상태는 전략적으로 좋지 않기 때문에 동맹을 맺은 두 이웃은 서로 마주 보는 변에 있으면 안 된다. 드워프 들은 정확하게 세 개의 이웃과 동맹을 맺고자 한다. 호빗들은 매우 무서워하며 네 개의 이웃 모두와 동맹을 맺고자 한다. ``` 다른 말로 하면 인간들을 제외하면 나머지 마을들은 특정한 개수의 이웃과 동맹을 하려고 하고 어느 이웃이 동맹이 되는지는 중요하게 생각하지 않는다. 인간들에게는 동맹관계를 맺은 이웃들이 서로 마주보는 변 쪽에 있으면 안 된다는 추가 조건이 있다. 위의 조건은 마을이 지도상의 어느 곳에 있던지 똑같이 적용되어야 한다. 예를 들면 드워프가 지도상에서 테두리에 붙어있다면 모든 3개의 이웃을 동맹으로 해야 할 것이고 드워프가 지도의 모서리에 있다면 어떻게 되어도 안심시킬 수 없다. 주어진 섬에 대한 정보를 통해 섬의 모든 거주자가 안심할 수 있는 동맹관계가 존재하는지 아닌지를 확인하라. 가능한 경우 실행 가능한 하나의 계획을 제시하라. 여러 개의 해가 존재할 경우 임의로 하나만 고르면 된다.
입력
첫째 줄에 섬의 크기인 $R$과 $C$가 주어진다. 다음 $R$개 줄에는 섬에 대한 설명이 주어진다. 각 줄에는 띄어쓰기로 구분된 $0$ 이상 $4$ 이하의 숫자가 $C$개 주어진다: ``` 0은 거주자가 없는 구역 1은 엘프들의 마을 2는 인간들의 마을 3은 드워프들의 마을 4는 호빗들의 마을 ``` (위 숫자들은 각 마을들이 동맹맺고자 하는 이웃의 개수와 같다는 점을 확인하라)
출력
해가 존재하지 않는다면 문자열 "Impossible!"(따옴표는 출력하지 않는다) 한 줄을 출력한다. 해가 존재한다면 가능한 동맹관계 중 한 가지를 아래와 같은 형식으로 출력한다. 각 구역은 문자로 이루어진 $3 \times 3$ 짜리 행렬로 표시된다. 거주자가 없는 구역의 경우 모두 .(점)으로 채워져 있어야 한다. 만약 마을이 있는 구역이라면 가운데에 $O$(알파벳 대문자)가 적혀있어야 하고 동맹관계를 맺은 방향으로 $X$(알파벳 대문자)를 표시해야 한다. 나머지 부분은 .(점)으로 채워져야 한다. 각 마을 형식에 따라 모든 가능한 동맹 배치 구조는 아래와 같다.
힌트
### 제약조건 모든 테스트 케이스에서 $1 \le R, C \le 70$ 이다. 이 중 $55$점에 해당하는 케이스는 $min(R, C) \le 10$ 이고 나머지 중 $15$점에 해당하는 케이스는 $R \times C \le 20$ 이다. 또 다른 $10$점에 해당하는 케이스에서는 섬에 거주자가 없는 구역과 인간들의 마을만 존재한다. (앞의 $55$점 부분과 겹치지 않는다.) 시간 제한은 $2$초, 메모리 제한은 $256MB$이다. #### 예제 입력 1 ``` 3 4 2 3 2 0 3 4 3 0 2 3 3 1 ``` #### 예제 출력 1 ``` ............ .OXXOXXO.... .X..X..X.... .X..X..X.... .OXXOXXO.... .X..X..X.... .X..X..X.... .OXXOXXOXXO. ............ ``` #### 예제 입력 2 ``` 1 2 2 1 ``` #### 예제 출력 2 ``` Impossible! ```