Informatica Online Judge

  타일 채우기 5 [1686 / 0696]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 9   Total Tried : 11


The Champion of this Problem (C++) : kdh9949 - ms / 1471byte
My Best Submission (C++) : N/A

[JKJeong 2016]

Background

새로운 타일 채우기 문제이다.

이번에는 $n×n$판에 $1×2$혹은 $1×1$ 타일들을 이용하여 전부 채우는 문제이다.

모든 타일은 회전 시켜서 놓을 수 있다.

이와 유사한 문제는 있었다.

하지만 이 문제에서는 또 다른 요소가 등장한다.

판의 각 장소 중에 $k$개의 타일을 놓지 못하는 핵심 장소들이 존재할 수 있다.

핵심 장소에는 직접 타일을 놓지 못한다. 즉 핵심 장소를 제외하고 전부 채워야 한다. 하지만 원할 때에는 $1×2$타일을 이용하여 이 곳으로 슬라이딩 시켜서 보호할 수 있도록 배치해야 한다.

이 때 $1×1$타일로는 보호할 수 없다. 반드시 $1×2$타일을 이용하여 보호해야 한다.

보호하는 예는 다음과 같다. (왼쪽 그림은 초기 상태, 다음 3가지 그림은 보호할 수 있도록 배치한 경우, 마지막 2가지 그림은 보호할 수 없는 경우)



물론 핵심 장소가 여러 개 있을 경우 하나의 $1×2$타일을 이용하여 여러 개의 핵심 요소를 보호할 수도 있다.

하지만 $1×2$타일은 오직 상, 하, 좌, 우로 최대 1칸만 움직일 수 있기 때문에 다음과 같은 경우는 허용되지 않는다. 즉, 가장 오른쪽 그림에서 왼쪽의 블록은 두 칸을 움직여 오른쪽 핵심요소를 보호할 수는 없다.





한 변의 길이가 $n$인 2차원 격자판과 각 핵심요소 $k$개의 위치가 주어질 때, 위 조건을 만족할 수 있도록 타일을 배치하는 경우의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 소의 수를 나타내는 자연수 $n$과 핵심 요소의 수를 나타내는 $k$가 공백으로 구분되어 입력된다.

다음 줄부터 $k$줄에 걸쳐서 각 핵심 요소의 행과 열의 좌표가 한 줄에 하나씩 공백으로 구분되어 입력된다.

[입력값의 정의역]

$1 ≤ n ≤ 10$
$0 ≤ k ≤ 8$

[sub task Info]

#1 : $k = 0$ (20%)
#2 : $k = 1$ (30%)
#3 : 추가 제한 없음.

Output

조건을 만족하는 경우의 수를 10억 7로 나눈 값을 출력한다.

IO Example

입력1
2 0

출력1
7

입력2
3 1
1 1

출력2
37

입력3
3 2
1 1
3 3

출력3
6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]