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

    Type: RemoteJudge 500ms 128MiB

[POI 2023/2024 R1] Budowa lotniska

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 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

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

3

2 1
..
..

2

2 2
X.
..

1

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

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

10

见附件
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

周四下午训练

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2025-2-20 8:00
End at
2025-2-20 17:00
Duration
9 hour(s)
Host
Partic.
6