Red Polyomino

AtCoder

IDabc211_e

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

3
5
#.#
...
..#

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.

#@#
@.@
@@#

Input #2

2
2
#.
.#

Output #2

0

There is no way to satisfy the condition.

Input #3

8
8
........
........
........
........
........
........
........
........

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Red Polyomino",
    "description": {
      "content": "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 `",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc211_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 `...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments