最大图样问题

Author: nex3z 2015-10-26

　　在最大正方形问题一篇中介绍了寻找最大正方形的方法，同样的方法稍加变化，即可用于寻找最大图样。

0. 问题描述

　　有M*N个正方形格子，其中一些格子涂成了蓝色，如图1中左图所示。求蓝色格子所能构成的最大十字的高度。图1中左图蓝色格子所能构成的最大十字高度为5，标记为深蓝色，如图1中右图。

图1

1. 思路

　　十字不同于正方形，难以将寻找大十字的问题分解为寻找小十字的问题，那么考虑将十字拆分成为更加规则的图形。对于高度为H的十字，其每一条边都是一个长度为H/2+1的条状图形（每条边都包含十字中心格子，由此建立起四条边之间的联系），将图1中右图分解为图2中的四张图。

图2

2. 预处理

　　对应图2中的四张图，使用g[1][i][j]、g[2][i][j]、g[3][i][j]、g[4][i][j]四张表，初始化：

for i = 1 : M + 1
    for j = 1 : N + 1
        if (isBlue[i][j])
            g[1 : 4][i][j] = 1
        else
            g[1 : 4][i][j] = 0

图3

3. 动态规划

　　对四张表进行更新，分别计算从左向右、从右向左、从上向下、从下向上四个方向连续蓝格的个数：

for i = 1 : M
    for j = 1 : N
        if (isBlue[i][j])
            g[1][i][j] = g[1][i][j - 1] + 1

for i = 1 : M
    for j = N : 1
        if (isBlue[i][j])
            g[2][i][j] = g[2][i][j + 1] + 1

for j = 1 : N
    for i = 1 : M
        if (isBlue[i][j])
            g[3][i][j] = g[3][i - 1][j] + 1

for j = 1 : N
    for i = M : 1
        if (isBlue[i][j])
            g[4][i][j] = g[4][i + 1][j] + 1

图4

4. 找最大值

　　使用result[i][j]记录图4的四张表里，第i行第j列的最小值：

for i = 1 : M
    for j = 1 : N
        result[i][j] = min(g[1:4][i][j])

图5

　　则result[i][j]表示以第i行第j列格子为中心，所能构成的最大十字边长（包含中心格子），其最大值即为最大十字的边长，则最大十字的高度为min(result[i][j]) * 2 – 1。图5中最大值为3，最大十字边长为3 * 2 – 1 = 5。

类似题目

http://acm.timus.ru/problem.aspx?space=1&num=1221