import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),sum=0; 
        // 创建 (n+1)行 (m+1)列 的数组,方便前缀和计算(从1开始索引)
        int[][] arr=new int[n+1][m+1];
        
        // 双重循环:遍历矩阵的每一个位置 (i,j)
        for(int i=1;i<=n;i++) {       // i:当前行
            for(int j=1;j<=m;j++) {   // j:当前列
                
                // 构建 二维前缀和数组
                // arr[i][j] = 左上角(1,1)到右下角(i,j) 的所有数字之和
                arr[i][j] = arr[i][j-1]     // 左边
                          + arr[i-1][j]     // 上边
                          - arr[i-1][j-1]   // 左上角重复减了,加回来
                          + sc.nextInt();   // 当前格子的值
                
                // 枚举所有子矩阵
                // 以 (i,j) 为右下角,遍历所有可能的左上角 (y,x)
                for(int x=1;x<=j;x++) {  // x:子矩阵左边界
                    for(int y=1;y<=i;y++){ // y:子矩阵上边界
                        
                        // 用前缀和公式,快速计算 子矩阵(y,x) ~ (i,j) 中 1的总数
                        int qi = arr[i][j]         // 大矩形总和
                                - arr[y-1][j]      // 减去上部分
                                - arr[i][x-1]      // 减去左部分
                                + arr[y-1][x-1];   // 加回重复减去的左上角
                        
                        // 计算这个子矩阵的 总元素个数
                        int s = (i - y + 1) * (j - x + 1);
                        
                        // 判断条件:1的数量 > 0的数量
                        // 0的数量 = 总元素 - 1的数量 = s - qi
                        if(qi > s - qi) {
                            sum++; // 满足条件,计数+1
                        }
                    }
                }//并不会重复计算,因为我们是固定右下角让左上角变化
            }
        }
        System.out.println(sum);
    }
}

更多推荐