动态规划: USACO5.3.4巨大的牛棚

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。

EXAMPLE
考虑下面的方格，它表示农夫约翰的农场，‘.'表示没有树的方格，‘#'表示有树的方格

　　　　 1 2 3 4 5 6 7 8
　　　　1 . . . . . . . .
　　　　2 . # . . . # . .
　　　　3 . . . . . . . .
　　　　4 . . . . . . . .
　　　　5 . . . . . . . .
　　　　6 . . # . . . . .
　　　　7 . . . . . . . .
　　　　8 . . . . . . . .
最大的牛棚是 5 x 5 的，可以建造在方格右下角的两个位置其中一个。

PROGRAM NAME: bigbrn
INPUT FORMAT
Line 1: 两个整数： N （1 <= N <= 1000），农场的大小，和 T （1 <= T <= 10，000）有树的方格的数量
Lines 2..T+1: 两个整数（1 <= 整数 <= N), 有树格子的横纵坐标

SAMPLE INPUT (file bigbrn.in)
8 3
2 2
2 6
6 3

OUTPUT FORMAT
输出文件只由一行组成，约翰的牛棚的最大边长。

SAMPLE OUTPUT (file bigbrn.out)

5

题解:

这段代码写的挺简练，还算满意。

这种矩阵式的题目之前没经验,弄了很久,开始思路是大致对的,但是搞错了方向。应该算每个单元向左上扩展的最大值，我想算根据一个点右下方向的情况判断当前的值。这样导致实际每次扩展，原来的状态都有所变化，就不是动态规划的思想了。

a.对于8*8的矩阵, ,将矩阵内的有树的地方都设置为0. 这个地方要注意,牛棚里面不能有树,但是牛棚边缘有树是合法的.因为没搞明白这个,最开始将树都设为-1,所以结果比答案小1.

b.矩阵里每个单元的值代表它朝左上方方向扩展可以构成正方形的边长.显然第一横行和第一竖行的值都为0,他们靠近边缘,都无法构成正方形.

c.从第2行开始遍历,如果一个单元,本身不是树(不为0),那么它的上方,左方,左上方的格子,这3个格子的最小值+1,即为这个格子向左上扩展出的正方形的最大值.

如

1 2

1 x

对于x, 其左方的单元可以最大能扩展成1的正方型,上方单元最大能扩展成为2的正方形.x单元本身最多能将左边的单元涵盖进去, 如果把上方最大的正方形单元涵盖了,左边就不满足条件了. 

d.填完所有的单元格,就能得到最大值.

our @trees = ([2,2], [2,6], [6,3]);
our $size = 8;
our @mtr;
our $max = 0;
for(@trees){
    my @t = @$_;
    $mtr[$t[0]][$t[1]] = 0;
}

for my $x (2.. $size){
    for my $y (2.. $size){
        if(!defined($mtr[$x][$y])){
            $mtr[$x][$y] = (sort ($mtr[$x-1][$y],$mtr[$x-1][$y-1],$mtr[$x][$y-1]))[0]+1;
            $max = $mtr[$x][$y] if($max< $mtr[$x][$y]);
        }
    }
}
print $max;