Problem5693--影厅选座

5693: 影厅选座

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

小爱和朋友们去看电影,一共需要购买 $k$ 张电影票。电影院共有 $n$ 排 $m$ 列,合计 $n\times m$ 个座位。有些位置已经占了,小爱希望和朋友能够做得近一点。
请你找在电影院里找一个矩形区域,该区域能够包含 $k$ 个空座,且面积达到最小。

Input

第一行:三个整数 $n,\ m, k$;
接下来 $n$ 行,每行 $m$ 个字符,X 表示座位已被预定,. 表示可选。

Output

若电影院空座不足 $k$ 个,输出 No Solution,否则输出一个整数,表示包含 $k$ 个空座的最小矩形面积。

Constraints

对于 $30\%$ 的数据,$1 \leq n,\ m \leq 50$;
对于 $60\%$ 的数据,$1 \leq n,\ m \leq 200$;
对于 $100\%$ 的数据,$1 \leq n,\ m \leq 800$;
$1 \leq k \leq n\times m$。

Sample 1 Input

3 3 4
XXX
XX.
XX.

Sample 1 Output

No Solution
影厅不足 $4$ 个空位。

Sample 2 Input

4 5 5
..XXX
X.XXX
XX.X.
XX...

Sample 2 Output

6
右下角 $2*3$ 的矩型中包含 $5$ 个空位。

HINT

题目来源:上海市计算机学会竞赛平台2020年6月月赛 丙组 T5

Source/Category