/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 行 N 列のマス目が与えられ、上から i 番目、左から j 番目のマスは、S_{i, j} が # なら黒く塗られており、. なら白く塗られています。
あなたは白く塗られたマスのうち、ちょうど K 個のマスを選んで赤く塗ります。以下の条件が満たされる塗り方は何通りありますか？
- 赤く塗られたマス(以下赤マスと呼ぶ)は連結である。すなわち、どの赤マスからどの赤マスへも赤マスのみを上下左右に辿って到達できる。
制約
- 1 \leq N \leq 8
- 1 \leq K \leq 8
- S_{i, j} は
#または. - N , K は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
K
S_{1, 1}S_{1, 2} \dots S_{1, N}
S_{2, 1}S_{2, 2} \dots S_{2, N}
\vdots
S_{N, 1}S_{N, 2} \dots S_{N, N}
出力
答えを出力せよ。
入力例 1
3 5 #.# ... ..#
出力例 1
5
#.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.#
上のように条件を満たす塗り方が 5 通りあります。
赤マスを @ で表しました。
#@# @.@ @@#
上の塗り方は連結でないので条件を満たしません。
斜めのマス同士は連結していないことに注意してください。
入力例 2
2 2 #. .#
出力例 2
0
条件を満たす塗り方はありません。
入力例 3
8 8 ........ ........ ........ ........ ........ ........ ........ ........
出力例 3
64678
Score : 500 points
Problem Statement
You are given a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left is painted black if S_{i, j} is # and white if S_{i, j} is ..
You will choose K of the white squares and paint them red. How many such ways to paint the grid satisfy the following condition?
- The squares painted red will be connected. That is, you will be able to get from any red square to any red square by repeatedly moving horizontally or vertically while only visiting red squares.
Constraints
- 1 \leq N \leq 8
- 1 \leq K \leq 8
- Each S_{i, j} is
#or.. - N and K are integers.
Input
Input is given from Standard Input in the following format:
N
K
S_{1, 1}S_{1, 2} \dots S_{1, N}
S_{2, 1}S_{2, 2} \dots S_{2, N}
\vdots
S_{N, 1}S_{N, 2} \dots S_{N, N}
Output
Print the answer.
Sample Input 1
3 5 #.# ... ..#
Sample Output 1
5
We have five ways to satisfy the condition as shown below, where @ stands for a red square.
#.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.#
Note that the way shown below does not satisfy the connectivity requirement since we do not consider diagonal adjacency.
#@# @.@ @@#
Sample Input 2
2 2 #. .#
Sample Output 2
0
There is no way to satisfy the condition.
Sample Input 3
8 8 ........ ........ ........ ........ ........ ........ ........ ........
Sample Output 3
64678