洛谷 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
解题思路:
一道DP题,用一个f[i][j]表示以(i,j)为正方形的右下顶点的边长,只有当a[i][j] = 1时,(i,j)才能作为正方形的右下角,对于一个已经确定的f[i][j]=x，它表明包括节点i，j在内向上x个节点，向左x个节点扫过的正方形中所有a值都为1；
状态转移方程:f[i][j] = min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1]) + 1;(a[i][j] == 1).
AC代码:

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,f[105][105],ans;
bool a[105][105];//因为只有0、1两种情况,用bool即可,节省空间
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            cin >> a[i][j];//存图 
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            if(a[i][j])//当a[i][j] == 1时 
                f[i][j] = min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1]) + 1, ans = max(ans,f[i][j]);
                //在(i,j)的上方、左方、左上方找一个边长最小的加1,更新f[i][j]的状态,并用ans更新答案 
    printf("%d",ans);
    return 0;
}