펜토미노

시간 제한1초메모리 제한512 MB

요약

N x M 보드의 0이 적힌 칸을 12가지 펜토미노로 정확히 한 번씩 덮는 배치를 찾아 출력한다.

난이도: 보통10점 중 7점
유형: 백트래킹, 완전 탐색
정답자: 아직 제출이 없습니다

문제

폴리오미노란 크기가 $1 \times 1$ 인 정사각형을 둘 이상 이어서 붙인 평면도형이며, 다음과 같은 조건을 만족해야 한다.

서로 다른 두 정사각형 $A$ , $B$ 가 인접하는 것은, 두 정사각형 $A$ , $B$ 가 겹치지 않고 한 변을 공유하는 것으로 정의된다.
서로 다른 두 정사각형 $A$ , $B$ 가 연결되어 있다는 것은, $A$ 와 $B$ 가 인접하거나, $A$ 와 인접하면서 $B$ 와 연결된 또 다른 정사각형 $C$ 가 존재한다는 것으로 정의된다.
폴리오미노를 이루는 정사각형 중 임의의 서로 다른 두 정사각형을 고르면 그 둘은 서로 연결되어 있다.

펜토미노는 정사각형 $5$ 개를 이어 붙인 폴리오미노를 의미한다. 펜토미노는 다음과 같이 $F$ , $I$ , $L$ , $N$ , $P$ , $T$ , $U$ , $V$ , $W$ , $X$ , $Y$ , $Z$ 모양으로 $12$ 가지가 있다.

F I L N P T U V W X Y Z

몽이는 크기가 $N \times M$ 인 직사각형 모양 보드 위에 $12$ 가지 펜토미노를 한 개씩 전부 놓으려고 한다. 보드는 크기가 $1 \times 1$ 인 정사각형 칸으로 나뉘어 있으며, 각각의 칸에는 $0$ 또는 $1$ 이 쓰여 있다. $0$ 이 쓰인 칸은 $60$ 개가 있다.

펜토미노를 놓을 땐 펜토미노의 각 정사각형이 반드시 보드의 한 칸을 정확하게 포함해야 하며, 펜토미노는 서로 겹칠 수 없다. 이때, 펜토미노는 $0$ 이 적힌 칸 위에만 놓을 수 있으며, $1$ 이 적힌 칸은 펜토미노가 덮을 수 없다. 또한, 각 펜토미노는 회전하거나 뒤집어서 보드에 올려놓을 수 있다.

위 조건을 만족하며 펜토미노 $12$ 개를 놓아 $0$ 이 적힌 모든 칸을 덮는 한 가지 경우를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 세로 크기 $N$ 과 가로 크기 $M$ 이 주어진다. ( $3 \le N$ , $M \le 100$ )

둘째 줄부터 $N$ 개의 줄에 걸쳐 보드에 쓰여 있는 숫자 0 또는 1이 공백으로 구분되어 주어진다. $i$ 번째 줄의 $j$ 번째 숫자는 위에서부터 $i$ 번째 칸, 왼쪽에서부터 $j$ 번째 칸에 쓰여 있는 숫자이다.

$12$ 가지 펜토미노를 겹치지 않게 한 개씩 놓아 0이 쓰여 있는 칸을 모두 펜토미노로 덮을 수 있는 경우의 입력만 주어진다.

출력

첫째 줄부터 $N$ 개의 줄에 걸쳐 보드의 상태를 공백으로 구분하여 출력한다.

$i$ 번째 줄의 $j$ 번째 값은 위에서부터 $i$ 번째 칸, 왼쪽에서부터 $j$ 번째 칸의 상태이다. $i$ 번째 줄의 $j$ 번째 칸에는 펜토미노를 놓았다면 펜토미노의 종류를 나타내는 알파벳(F, I, L, N, P, T, U, V, W, X, Y, Z)을 출력하고, 펜토미노를 놓을 수 없는 칸이면 1을 출력한다.

만족하는 경우가 여러 가지라면 그중 아무거나 하나를 출력한다.

예제6

예제 1

입력

6 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예상 출력

N T T T X W W P P P
N N T X X X W W P P
L N T U X U F W Z Z
L N Y U U U F F Z V
L Y Y Y Y F F Z Z V
L L I I I I I V V V

예제 2

입력

8 8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

예상 출력

T I I I I I P P
T T T N N X P P
T N N N X X X P
V V V 1 1 X F F
V U U 1 1 F F Y
V U W W Z Z F Y
L U U W W Z Y Y
L L L L W Z Z Y

예제 3

입력

7 11
1 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 0
0 0 0 1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 0
0 0 0 1 0 1 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0 1

예상 출력

1 P P P I I I I I F 1
V P P 1 T 1 X 1 F F F
V 1 T T T X X X Z 1 F
V V V 1 T 1 X 1 Z Z Z
W 1 L L L L U U U 1 Z
W W L 1 Y 1 U 1 U N N
1 W W Y Y Y Y N N N 1

예제 4

입력

8 11
0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

예상 출력

V V V I I I I I U U U
V 1 1 1 1 1 1 1 U X U
V 1 1 1 1 1 1 1 X X X
Y 1 1 1 1 1 1 1 F X N
Y 1 1 1 1 1 1 1 F F N
Y Y W Z Z P T F F N N
Y W W Z P P T T T N L
W W Z Z P P T L L L L

예제 5

입력

8 11
1 1 0 0 1 1 1 0 0 1 1
1 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1
0 0 1 1 0 0 0 1 1 0 0
0 0 1 1 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1 0 1

예상 출력

1 1 W W 1 1 1 U U 1 1
1 W W F T T T U Z Z 1
1 W F F F T V U U Z 1
P P 1 1 F T V 1 1 Z Z
P P 1 1 V V V 1 1 L N
P X Y Y Y Y L L L L N
X X X Y I I I I I N N
1 X 1 1 1 1 1 1 1 N 1

예제 6

입력

11 10
1 1 1 0 0 0 0 1 1 1
1 1 0 0 1 1 0 0 1 1
1 1 0 0 1 1 1 0 1 1
0 0 0 0 1 1 0 0 0 1
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 1
0 0 0 0 1 1 1 0 1 1
0 0 0 0 0 0 0 0 1 1
1 1 0 0 0 0 0 0 1 1
1 1 0 0 1 1 0 0 1 1
1 1 0 0 1 1 0 0 1 1

예상 출력

1 1 1 F F W W 1 1 1
1 1 F F 1 1 W W 1 1
1 1 P F 1 1 1 W 1 1
L L P P 1 1 U U X 1
L T P P 1 1 U X X X
L T T T 1 1 U U X 1
L T N N 1 1 1 I 1 1
V V V N N N Y I 1 1
1 1 V Z Z Y Y I 1 1
1 1 V Z 1 1 Y I 1 1
1 1 Z Z 1 1 Y I 1 1