Informatica Online Judge

  격자상의 경로 [2314 / 090A]

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


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 167byte
My Best Submission (C++) : N/A

[KOI 2014]

Background

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 O표시가 되어 있다. (단, 1번 칸과 N×M번 칸은 O표시가 되어 있지 않다. 또한, O표시가 되어 있는 칸은 최대 한 개이다. 즉, O표시가 된 칸이 없을 수도 있다.)

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 O표시가 되어 있다.




격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다.

조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다.
(즉, 대각선 방향으로는 이동할 수 없다.)

조건 2: 격자에 O로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

1→2→3→8→9→10→15
1→2→3→8→13→14→15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.

Input

입력의 첫째 줄 에는 격자의 행의 수와 열의 수를 나타내는 두 정 수 N 과 M(1≤N,M≤15), 그리고 O로 표시 된 칸의 번호를 나타내는 정수 K(K=0또는1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는 데, 이는 O로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

Output

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.

IO Example

입력
3 5 8

출력
9

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