Geometric Gridlock

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

요약

빈 h×w 격자를 열두 가지 펜토미노 모양으로 나누되, 변을 맞댄 두 영역이 같은 모양이 되지 않도록 채워야 한다.

난이도: 보통10점 중 7점
유형: 백트래킹, 구현, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

Pentominous is a grid logic puzzle based on the twelve pentominoes. A pentomino is a polygon formed by connecting five equal-sized squares edge to edge.

Figure G.1: The twelve pentominoes (up to mirroring and rotations) and their names.

The goal of this puzzle is to divide a grid into regions of size $5$ (that is, pentominoes), so that no two regions that share a side have the same shape. You are allowed to rotate and mirror the pentominoes, but such rotations and reflections count as the same shape. The twelve possible shapes can be seen in Figure \ref{fig:pentominoes}.

In a normal Pentominous puzzle, the player is given some pre-filled cells, for which the shape of their region is already predetermined. In this problem, you are working with a completely blank grid of dimensions $h\times w$ , and your task is to create any valid arrangement of pentominoes.

입력

The input consists of:

One line with two integers $h$ and $w$ ( $1 \le h,w \le 100$ ), the height and width of the grid.

출력

If there is no valid $h\times w$ Pentominous grid, output "no". Otherwise, output "yes", followed by $h$ lines of width $w$ each, a possible grid using the letters from Figure G.1. If there is more than one solution, any one of them will be accepted.

예제5

예제 1
입력
```
3 5
```
예상 출력
```
yes
UUXUU
UXXXU
UUXUU
```
예제 2
입력
```
2 10
```
예상 출력
```
yes
LLLLNNNPPP
LIIIIINNPP
```
예제 3
입력
```
99 17
```
예상 출력
```
no
```

예제 4

입력

6 10

예상 출력

yes
IPPYYYYVVV
IPPXYLLLLV
IPXXXFZZLV
ITWXFFFZUU
ITWWNNFZZU
TTTWWNNNUU

예제 5
입력
```
1 5
```
예상 출력
```
yes
IIIII
```