洛谷1387 最大正方形

本题地址： http://www.luogu.org/problem/show?pid=1387

题目描述

在一个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

题解

枚举/动态规划

本题有两种做法：

1.枚举：

枚举矩阵中的每一个点，然后以这个点为左上角顶点逐层向右下方扩展正方形的面积，

当遇到0时，把此点扩展的正方形层数（边长）的平方记录为当前点扩展的最大面积（还要注意边界处理）。

最后比较各点扩展的面积，得出最大正方形面积。

2.动态规划：

如果数据范围再大一些的话，枚举法就会显得力不从心了。我们可以考虑用动态规划解决，其思想也是非常巧妙的。

定义f[i,j]为以（i，j）为右下角顶点的最大正方形边长。

当a[i,j]=1时，f[i,j]=min{f[i,j-1],f[i-1,j],f[i-1,j-1]}+1;

最大边长：ans=max{f[i,j]}   (1<=i<=n,1<=j<=m)

最大面积：ans*ans

下面附上代码。

代码

var    n,m,i,j,max:longint;    a,f:Array[-1..101,-1..101] of longint;  function min(a,b,c:longint):longint;  begin    if a>b then a:=b;    if a>c then a:=c;    exit(a);  end;  begin    readln(n,m);    for i:=1 to n do      begin        for j:=1 to n do          read(a[i,j]);        readln;      end;    for i:=n downto 1 do    for j:=m downto 1 do     begin     if a[i,j]=1 then f[i,j]:=min(f[i+1,j],f[i,j+1],f[i+1,j+1])+1;     if f[i,j]>max then max:=f[i,j];     end;  if max=0 then writeln(1) else writeln(max);  end.  

（本文系笔者原创，未经允许不得转载）

转载于:https://www.cnblogs.com/yzm10/p/4752937.html