洛谷P1387 最大正方形

最大正方形

题目描述

在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。

输入输出格式

输入格式：
输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.

输出格式：
一个整数，最大正方形的边长

输入输出样例

输入样例#1：

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
输出样例#1：
2

题目分析

一题非常标准的多维动归，具有最优子结构及无后效性的性质。
数组f[i,j]表示以i,j为正方形右下角时的最大边长。并且可以发现它的大小取决于min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1；
于是可以列出动态转移方程：
f[i,j]=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1

最后从f数组中选择最大值并输出。

详见代码~

program LargeSquare;
var n,m,i,j,max:longint;
a,f:array[0..100,0..100]of longint;//数组a储存每个位置的数据，数组f为动归数组

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

begin
  readln(n,m);
  for i:=1 to n do
    for j:=1 to m do
      read(a[i,j]);

  fillchar(f,sizeof(f),0);

  for i:=1 to n do
    for j:=1 to m do
    begin
      if a[i,j]=0 then continue;//只有1的位置可成为正方形的一部分
      f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1;//动转方程详见上
    end;

  max:=0;

  for i:=1 to n do
    for j:=1 to m do
      if max<f[i,j] then max:=f[i,j];

  writeln(max);
end.