P1387 最大正方形 DP

  • 时间:
  • 浏览:
  • 来源:互联网

在这里插入图片描述
输入

15 10
0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 0 0 1 0 1 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 0
1 0 0 0 1 1 1 1 1 0
1 0 0 0 1 1 1 1 1 0
1 1 0 0 1 1 1 1 1 0
1 0 0 0 1 1 1 1 1 0
1 0 0 0 0 1 1 1 1 0
1 0 0 0 0 1 1 1 1 0
0 0 1 0 0 1 1 1 1 0

输出

5

解题思路:

解题思路

以(i,j)点当正方形右下角,f[i][j]为最大边长

  • 如果他本身为1,判断能形成多大的正方形的主要看左,上,左上那个的最小值;
  • 如果他本身是0,肯定组不成正方形,还是0;
    在这里插入图片描述领会一下,如果该点为1,最小值+1,就是以当前点为右下角组成的最大正方形边长

DP的式子:
if(f[i][j]==1)
f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;

运行演示
运行演示
代码注意

  • 出现f[i-1][j-1]一般是存数从1开始,可以减少判断
  • 判断三个数min(min(a,b),c)
  • 输入不一定是正方形

AC代码

using namespace std;
#include <iostream>
#include <algorithm>
#include <cmath>
int a[102][102];
int f[102][102]; 

int main ()
{
    int n,m,i,j;
	cin>>n>>m;
	int max=-1;
	for(i=1;i<=n;i++)
	{
	   for(j=1;j<=m;j++)
	   {
	      cin>>a[i][j];	
	   	  if(a[i][j]==1)
	   	  {
	        f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;	   	  	
		  }
		  if(max<f[i][j])
		  {
		  	max=f[i][j];
		  }
	   }	
	} 
	cout<<max;
}

本文链接http://www.dzjqx.cn/news/show-617184.html