5693: 影厅选座
[Creator : ]
Description
小爱和朋友们去看电影,一共需要购买 $k$ 张电影票。电影院共有 $n$ 排 $m$ 列,合计 $n\times m$ 个座位。有些位置已经占了,小爱希望和朋友能够做得近一点。
请你找在电影院里找一个矩形区域,该区域能够包含 $k$ 个空座,且面积达到最小。
请你找在电影院里找一个矩形区域,该区域能够包含 $k$ 个空座,且面积达到最小。
Input
第一行:三个整数 $n,\ m, k$;
接下来 $n$ 行,每行 $m$ 个字符,X 表示座位已被预定,. 表示可选。
接下来 $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$。
对于 $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$ 个空位。