【SSL】农田个数-白红宇

【SSL】农田个数

阅读量：338 次

发布时间：2019-03-04

本文共 1453 字，大约阅读时间需要 4 分钟。

这个问题要求我们计算一个N×M网格中满足特定条件的正方形数量。两个正方形必须满足至少一个条件：边长不同或左上角不同。我们可以通过动态规划的方法来解决这个问题。

方法思路

定义动态规划数组：我们使用一个二维数组f，其中f[i][j]表示以(i, j)为右下角的最大正方形的边长。

计算最大正方形边长：对于每个网格点(i, j)，如果当前点是农田（即值为1），则f[i][j] = min(f[i-1][j], f[i-1][j-1], f[i][j-1]) + 1。否则，f[i][j]为0。

统计正方形数量：我们使用一个一维数组f1来记录每个边长的正方形数量。然后，从最大的边长开始累加，得到总数。

解决代码

#include 
   
    
#include 
    
     
#include 
     
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    char grid[n+1][m+1];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
        }
    }
    
    int f[n+1][m+1], f1[10001], s[10001], ans = 0;
    int mx = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] == '0') {
                f[i][j] = 0;
                continue;
            }
            int a = f[i-1][j], b = f[i-1][j-1], c = f[i][j-1];
            f[i][j] = min(a, min(b, c)) + 1;
            if (f[i][j] > mx) {
                mx = f[i][j];
            }
            f1[f[i][j]]++;
        }
    }
    
    for (int i = mx; i >= 1; --i) {
        if (i > 0) {
            s[i] = s[i+1] + f1[i];
            ans += s[i];
        }
    }
    
    cout << ans << endl;
    return 0;
}

代码解释

读取输入：首先读取输入的N和M，然后读取网格数据。

初始化数组：f数组用于存储每个网格点的最大正方形边长，f1数组记录每个边长的正方形数量，s数组用于累加结果。

计算最大正方形边长：遍历每个网格点，根据上、左、左上三个方向的最大正方形边长计算当前点的最大边长。

统计正方形数量：从最大的边长开始，累加每个边长的正方形数量，得到最终结果。

这个方法通过动态规划高效地计算了所有满足条件的正方形数量，确保了结果的准确性和效率。

转载地址：http://ygue.baihongyu.com/

你可能感兴趣的文章