码蹄集MC0507鱼肚里掏出剑java
·

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);
}
}
更多推荐

所有评论(0)