难度：普及/提高-

题目描述

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

输入输出格式

输入格式:

        输入文件第一行为两个整数n，m(1≤n,m≤100)，接下来n行，每行m个数字，用空格隔开，0或1。

输出格式:

一个整数,最大正方形的边长。

输入输出样例:

Sample input

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

Sample output

2

题解

        题目考察二维动态规划及递推。
        若设f(x,y)示以此点为左上点正方形的最大边长。则易得:

        注意若点(x,y)为0或者超出边界，则f(x,y)=0，从f(x,y)中找出最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>

using namespace std;
int op[105][105], n, m;
int ans[105][105] = {0};

int main() {
    cin >> n >> m;
    for (register int i = 1; i <= n; i++)
        for (register int j = 1; j <= m; j++)cin >> op[i][j];
    int res = 0;
    for (register int i = n; i >= 1; i--)
        for (register int j = m; j >= 1; j--) {
            if (op[i][j] == 0)continue;
            ans[i][j] = min(ans[i + 1][j], min(ans[i][j + 1], ans[i + 1][j + 1])) + 1;
            res = max(res, ans[i][j]);
        }
    cout << res;
    return 0;
}