为什么不能考虑从左上角求最大值呢
查看原帖
为什么不能考虑从左上角求最大值呢
694341
hhhh_213楼主2022/9/8 17:56
#include <iostream>

using namespace std;

const int N = 1010;

int g[N][N], f[N][N];
int n, m;

bool check(int x, int y, int len)
{
    for(int i = x - len; i <= x; i++)
        if(!g[i][y])    return false;
    
    for(int j = y - len; j <= y; j++)
        if(!g[x][j])    return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
        {
            cin >> g[i][j]; if(g[i][j]) f[i][j] = 1;
        }    
    
    int res = 0;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
        {
            if(g[i][j] == 1)
            {
                if(g[i - 1][j - 1] == 1)
                {
                    if(check(i, j, f[i - 1][j - 1]))   f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j]);
                }
            }
            res = max(res, f[i][j]);
        }
        
    cout << res * res << endl;
    
    return 0;
}

f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j]) 为什么不能直接考虑左上角来直接递增正方形的边长呢,任意一个不都由上一个边长小1的转移而来吗

2022/9/8 17:56
加载中...