【SSL】农田个数-白红宇

【SSL】农田个数

阅读量：338 次

发布时间：2019-03-04

本文共 1419 字，大约阅读时间需要 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/

你可能感兴趣的文章

Objective-C实现clearBit清除位算法（附完整源码）