AdditionalFile4047.zip

P9921 [POI 2023/2024 R1] Budowa lotniska

题目背景

译自 XXXI Olimpiada Informatyczna - I etap Budowa lotniska。

题目描述

给你一个 $n\times n$ 的地图，地图上有 . 有 X。

求出最大的 $k$，使得：

在地图上能找到 $m(m\leq 2)$ 个 $1\times k$ 或 $k\times 1$ 的长条，使得长条不交且长条内全是 .。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，描述地图。

输出格式

一行一个非负整数，最大的 $k$。

输入输出样例 #1

输入 #1

5 2
.X...
.XXXX
XX...
.....
.X.X.

输出 #1

3

输入输出样例 #2

输入 #2

2 1
..
..

输出 #2

2

输入输出样例 #3

输入 #3

2 2
X.
..

输出 #3

1

输入输出样例 #4

输入 #4

10 2
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
..........
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

输出 #4

5

输入输出样例 #5

输入 #5

10 2
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X

输出 #5

10

输入输出样例 #6

输入 #6

见附件

输出 #6

531

说明/提示

样例解释：

.X...
.XXXX
XX..2
111.2
.X.X2

对于所有数据，$1\leq n\leq1500$，$1\leq m\leq2$，地图上只有 . 和 X。

子任务编号	附加限制	分值
1	$m=1$	20
2	$n\leq 30$	22
3	$n\leq 300$	23
4		35

#4047. 「POI 2023/2024 R1」Budowa lotniska

标签: 传统 | 时间限制: 8000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXXI Olimpiada Informatyczna – I etap Budowa lotniska

Bajtazar 正在设计一个新的机场，它将建在 Bajtocja 的中心。机场是一个 $n \times n$ 平方米的正方形，按照规划，它被划分为 $n^{2}$ 个 $1 \times 1$ 平方米的小方格。其中一些方格已经被计划的建筑物占据了（出发和到达大厅，空中交通管制塔，飞机库）。Bajtazar 的任务是为 $m\ (m \leq 2)$ 条同样长度的跑道找到合适的位置。

每条长度为 $k$ 的跑道必须由 $k$ 个相邻的空方格组成，形成一个 $1 \times k$ 或 $k \times 1$ 平方米的矩形。跑道之间不能相交，也不能包含被占据的方格。当两条跑道没有共同的格子时，我们说它们是不相交的。Bajtazar 想知道能够在机场上规划的跑道的最大长度是多少。

输入格式

第一行包含两个整数 $n,m$ $(1 \leq n \leq 1500,1 \leq m \leq 2)$，分别表示机场的边长和要建造的跑道的数量。

接下来的 $n$ 行描述了机场的情况；每行有一个 $n$ 个字母组成的字符串，由 X（表示被占据的方格）和 .（表示空的方格）组成。

输出格式

输出一行一个整数 $k$，表示能够规划的跑道的最大长度。如果他不能规划出满足条件的跑道，则输出 $0$。

样例 1

输入

5 2
.X...
.XXXX
XX...
.....
.X.X.

输出

3

下图展示了一种可能的长度为 $3$ 的跑道的布局：

.X...
.XXXX
XX..2
111.2
.X.X2

样例 2

见附加文件下 [bud1ocen.in](file:bud1ocen.in) 和 [bud1ocen.out](file:bud1ocen.out)。

该样例满足 $n=2, m=1$，所有的方格都是空的。答案是 $2$。

样例 3

见附加文件下 [bud2ocen.in](file:bud2ocen.in) 和 [bud2ocen.out](file:bud2ocen.out)。

该样例满足 $n=2, m=2$，有一个方格被占据了。答案是 $1$。

样例 4

见附加文件下 [bud3ocen.in](file:bud3ocen.in) 和 [bud3ocen.out](file:bud3ocen.out)。

该样例满足 $n=10, m=2$，除了第 $5$ 行，所有的方格都被占据了。答案是 $5$。

样例 5

见附加文件下 [bud4ocen.in](file:bud4ocen.in) 和 [bud4ocen.out](file:bud4ocen.out)。

该样例满足 $n=1500, m=2$，除了第 $31$ 列，所有的方格都被占据了，而第 $31$ 列只有 $2$ 个方格被占据了。答案是 $531$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$m=1$	$20$
$2$	$n \leq 30$	$22$
$3$	$n \leq 300$	$23$
$4$	无附加限制	$35$