最大图样问题

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

0. 问题描述

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

图1

图1

1. 思路

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

图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。注意在原图的四周各加了一行(列)0。

图3

图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

图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:

图5

图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