D - Count Simple Paths 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 425 点

問題文

H 行 W 列のマス目があります。マス目の上から i 番目、左から j 番目のマスをマス (i,j) と表記します。

マス (i,j) は S_{i,j} が . のとき空きマスであり、# のとき障害物があります。

ある空きマスを出発し、上下左右に隣接するマスへの移動を K 回行う方法であって、障害物のあるマスを通らず、同じマスを 2 回以上通らないようなものの個数を数えてください。

具体的には、長さ K+1 の列 ((i_0,j_0),(i_1,j_1),\dots,(i_K,j_K)) であって、以下を満たすものの個数を数えてください。

  • 各 0 \leq k \leq K について、 1 \leq i_k \leq H, 1 \leq j_k \leq W かつ S_{i_k,j_k} は . である
  • 各 0 \leq k \leq K-1 について、 |i_{k+1}-i_k| + |j_{k+1}-j_k| = 1
  • 各 0 \leq k < l \leq K について、 (i_k,j_k)\neq (i_l,j_l) である

制約

  • 1 \leq H,W \leq 10
  • 1 \leq K \leq 11
  • H,W,K は整数
  • S_{i,j} は . または #
  • 空きマスが少なくとも 1 つ存在する

入力

入力は以下の形式で標準入力から与えられる。

H W K
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}

出力

答えを出力せよ。

入力例 1

2 2 2
.#
..

出力例 1

2

可能な経路は、以下の 2 通りです。

  • (1,1) \to (2,1) \to (2,2)
  • (2,2) \to (2,1) \to (1,1)

入力例 2

2 3 1
.#.
#.#

出力例 2

0

入力例 3

10 10 11
....#..#..
.#.....##.
..#...##..
...#......
......##..
..#......#
#........#
..##......
.###....#.
...#.....#

出力例 3

218070

Score : 425 points

Problem Statement

There is a grid of H \times W cells. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

Cell (i, j) is empty if S_{i,j} is ., and blocked if it is #.

Count the number of ways to start from an empty cell and make K moves to adjacent cells (up, down, left, or right), without passing through blocked squares and not visiting the same cell more than once.

Specifically, count the number of sequences of length K+1, ((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K)), satisfying the following.

  • 1 \leq i_k \leq H, 1 \leq j_k \leq W, and S_{i_k, j_k} is ., for each 0 \leq k \leq K.
  • |i_{k+1} - i_k| + |j_{k+1} - j_k| = 1 for each 0 \leq k \leq K-1.
  • (i_k, j_k) \neq (i_l, j_l) for each 0 \leq k < l \leq K.

Constraints

  • 1 \leq H, W \leq 10
  • 1 \leq K \leq 11
  • H, W, and K are integers.
  • Each S_{i,j} is . or #.
  • There is at least one empty cell.

Input

The input is given from Standard Input in the following format:

H W K
S_{1,1}S_{1,2}\dots S_{1,W}
S_{2,1}S_{2,2}\dots S_{2,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}

Output

Print the answer.

Sample Input 1

2 2 2
.#
..

Sample Output 1

2

Here are the two possible paths:

  • (1,1) \rightarrow (2,1) \rightarrow (2,2)
  • (2,2) \rightarrow (2,1) \rightarrow (1,1)

Sample Input 2

2 3 1
.#.
#.#

Sample Output 2

0

Sample Input 3

10 10 11
....#..#..
.#.....##.
..#...##..
...#......
......##..
..#......#
#........#
..##......
.###....#.
...#.....#

Sample Output 3

218070