#P9921. [POI 2023/2024 R1] Budowa lotniska

[POI 2023/2024 R1] Budowa lotniska

题目背景

译自 XXXI Olimpiada Informatyczna - I etap Budowa lotniska

题目描述

给你一个 n×nn\times n 的地图,地图上有 .X

求出最大的 kk,使得:

在地图上能找到 m(m2)m(m\leq 2)1×k1\times kk×1k\times 1 的长条,使得长条不交且长条内全是 .

输入格式

第一行两个正整数 n,mn,m

接下来 nn 行,描述地图。

输出格式

一行一个非负整数,最大的 kk

输入数据 1

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

输出数据 1

3

输入数据 2

2 1
..
..

输出数据 2

2

输入数据 3

2 2
X.
..

输出数据 3

1

输入数据 4

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

输出数据 4

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

531

提示

样例解释:

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

对于所有数据,1n15001\leq n\leq15001m21\leq m\leq2,地图上只有 .X

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