列表

详情


NC23760. 填坑

描述

给你一个n×n的网格,每个格子或者是平地,或者是坑。好心的Mike决定找一块k×k的格子,将这些格子中的坑全部填成平地。

Mike希望填完之后最大的平地联通块的格子数量最多,请你输出最后最大的平地联通块的格子数量的最大值。两块平地直接联通当且仅当他们有一条公共边。

输入描述

第一行有两个整数n,k。(1<=k<=n<=500)

接下来n行,每行n个整数,其中0表示这个格子是坑,1表示这个格子是平地。

输出描述

一行一个整数,表示填坑之后最大的平地联通块的格子数量的最大值。

示例1

输入:

5 2
1 1 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 1 0
0 0 0 0 1

输出:

10

示例2

输入:

5 3
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1

输出:

25

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

上一题