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