No.3710 Universal Tiles
タグ : / 解いたユーザー数 55
作問者 :
UT0911
/ テスター :
sclara
👑 
Rino-program
Problem Statement
Yu-T is planning to replace the tiles on a wall. Yu-T has $N$ desired patterns.
The $i$-th desired pattern is represented by $M$ strings of length $M$. If the $k$-th character of the string
$S_{i,j}$ is #, the cell in the $j$-th row from the top and the $k$-th column from the left "must be a black cell"; if it is ., that cell "does not have to be a black cell".
Each desired pattern may be rotated in units of $90$ degrees. However, it cannot be flipped horizontally or vertically.
Among the $M\times M$ tilings that can satisfy all the desired patterns, consider one with the minimum number of black cells, and find its number of black cells.
Constraints
- $N, M$ are integers
- $1 \leq N \leq 8$
- $1 \leq M \leq 10$
- $S_{i,j}$ is a string of length $M$ consisting of
#and.
Input
$N$ $M$
$S_{1, 1}$
$\vdots$
$S_{1, M}$
$\vdots$
$S_{N, 1}$
$\vdots$
$S_{N, M}$
Output
Find the minimum number of black cells contained in an $M \times M$ tiling that satisfies all the desired patterns.
Print a newline at the end.
Sample
Sample 1
Input
3 4 #### .... .... .... .... .##. .##. .... .... .... .... ...#
Output
8
The desired patterns are as follows.
#### .... ....
.... .##. ....
.... .##. ....
.... .... ...#
Rotate the $3$-rd desired pattern by $180$ degrees. With the following pattern, the number of black cells is $8$.
It cannot be reduced to $7$ or fewer, so this is the minimum.
####
.##.
.##.
....
Sample 2
Input
2 5 #...# #...# #...# #...# .###. ##### ..#.. ..#.. ..#.. ..#..
Output
15
Sample 3
Input
2 5 #.#.# .#.#. #.#.# .#.#. #.#.# .#.#. #.#.# .#.#. #.#.# .#.#.
Output
25
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。