最大图样问题 Author: nex3z 2015-10-26 在最大正方形问题一篇中介绍了寻找最大正方形的方法，同样的方法稍加变化，即可用于寻找最大图样。 0. 问题描述 有M*N个正方形格子，其中一些格子涂成了蓝色，如图1中左图所示。求蓝色格子所能构成的最大十字的高度。图1中左图蓝色格子所能构成的最大十字高度为5，标记为深蓝色，如图1中右图。 1. 思路 十字不同于正方形，难以将寻找大十字的问题分解为寻找小十字的问题，那么考虑将十字拆分成为更加…Read more ACM ACM, DP
最大正方形问题 Author: nex3z 2015-10-26 0. 问题描述 有M*N个正方形格子，其中一些格子涂成了蓝色，如图1所示。求蓝色格子所能构成的最大正方形边长。图1中蓝色格子所能构成的最大正方形边长为3。 1. 预处理 使用g[i][j]表示以第i行第j列的格子为右下角，所能构成的最大正方形的边长。对g[i][j]进行初始化： 如果格子为白色，令g[i][j] = 0； 如果格子为蓝色，令g[i][j] = 1。 得到结果如图2。注意…Read more ACM ACM, DP