洛谷 P1387 最大正方形 动规
题目链接: 点我跳转
题目大意: 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形
题目分析: 如果在某一位置存在一个k阶的正方形(黑色)那么内部一定存在4个k-1阶的小正方形(彩色)
我们令 表示在这个位置,存在一个边长为的正方形,那么我们的状态转移方程就是
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define mmax(a,b,c) max(max((a),(b)),(c))
int data[105][105],dp[105][105][105];
int main(){
int n,m;
bool all_0 = true;
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>data[i][j];
dp[i][j][1] = data[i][j];
if(dp[i][j][1])all_0 = false;//特判一下是不是全是0
}
if(all_0){cout<<"0";return 0;}//特判
for(int l = 2;l<=min(n,m);l++){
bool ok = false;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(dp[i][j][l-1] &&
dp[i+1][j][l-1] &&
dp[i][j+1][l-1] &&
dp[i+1][j+1][l-1])
dp[i][j][l] = 1,ok = true;
if(!ok){
cout<<l-1;return 0;//如果没有边长为l的正方形
}
}
cout<<min(n,m);
return 0;
}