动态规划算法题！错了一个点

Question

P1387 最大正方形

最大正方形

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

2

显示第九个点错，没找到代码问题在哪，哭了，求解答

代码如下

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n, m, i, j, a[105][105], ma, k;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> a[i][j];
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            int flg = 1;
            k = a[i - 1][j - 1];
            for (; k >= 0; k--) {
                if (a[i - k][j] == 0 || a[i][j - k] == 0) {
                    flg = 0;
                    break;
                }
            }
            if (flg == 1)  a[i][j] += a[i - 1][j - 1];
            ma = max(ma, a[i][j]);
            //cout << "i=" << i << " j=" << j << " a[i][j]=" << a[i][j] << endl;
        }
    }
    cout << ma;
    return 0;
}

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

这个问题是一个动态规划的经典问题，需要找出一个不包含 0 的最大正方形，并输出其边长。

首先，你的代码有一个逻辑错误。在这行代码中：

k = a[i - 1][j - 1];

你将 k 初始化为 a[i - 1][j - 1]，但实际上应该是初始化为以当前点为右下角的正方形的边长。所以这里应该将 k 初始化为当前点 (i, j) 右下方的正方形的边长，而不是 (i-1, j-1)。

修改为：

k = min(a[i - 1][j], a[i][j - 1]);
k = min(k, a[i - 1][j - 1]) + 1;

这样就能正确初始化 k。

接下来，你的动态规划转移有些问题。你的目标是找出以当前点 (i, j) 为右下角的最大正方形的边长，但你的转移逻辑中出现了错误。

正确的转移逻辑应该是：以 (i, j) 为右下角的正方形的边长取决于三个方向的最小值（左边、上边、左上角），然后加上当前点的值（因为当前点是右下角，如果为1则可以构成更大的正方形）。

所以修改为：

if (a[i][j] == 1) {
    a[i][j] = min(a[i - 1][j], a[i][j - 1]);
    a[i][j] = min(a[i][j], a[i - 1][j - 1]) + 1;
    ma = max(ma, a[i][j]);
}

这样就能正确地进行动态规划转移了。

修改完成后的代码如下所示：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int n, m, i, j, a[105][105], ma, k;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> a[i][j];

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i][j] == 1) {
                a[i][j] = min(a[i - 1][j], a[i][j - 1]);
                a[i][j] = min(a[i][j], a[i - 1][j - 1]) + 1;
                ma = max(ma, a[i][j]);
            }
        }
    }

    cout << ma;

    return 0;
}

这样应该就能得到正确的结果了。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订