AT_abc378_d [ABC378D] Count Simple Paths

[problemUrl]: https://atcoder.jp/contests/abc378/tasks/abc378_d $ 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\

入力は以下の形式で標準入力から与えられる。 > $ 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\ \leq\ H,W\ \leq\ 10 $ - $ 1\ \leq\ K\ \leq\ 11 $ - $ H,W,K $ は整数 - $ S_{i,j} $ は `.` または `#` - 空きマスが少なくとも $ 1 $ つ存在する ### Sample Explanation 1 可能な経路は、以下の $ 2 $ 通りです。 - $ (1,1)\ \to\ (2,1)\ \to\ (2,2) $ - $ (2,2)\ \to\ (2,1)\ \to\ (1,1) $