ccf 202104-2 邻域均值

暴力解法

import java.util.Scanner;

public class NeighborAvgOld {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int L = sc.nextInt();
        int r = sc.nextInt();
        int t = sc.nextInt();
        sc.nextLine();
        int[][] arr = new int[n][n];
        int[][] sum_arr = new int[n+1][n+1];
        for(int i = 0; i < n; i++){
            String line = sc.nextLine();
            String[] str_arr = line.split(" ");
            for(int j = 0; j < n; j++){
                arr[i][j] = Integer.parseInt(str_arr[j]);
                sum_arr[i+1][j+1] = sum_arr[i][j+1] + sum_arr[i+1][j]
                        - sum_arr[i][j] + arr[i][j];
            }
        }
        int total_count = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int tmp_sum = 0;
                int count = 0;
                for(int a = i-r; a <= i+r; a++){
                    for(int b = j-r; b <= j+r; b++){
                        if(a >= 0 && a < n && b >= 0 && b < n){
                            tmp_sum+=arr[a][b];
                            count++;
                        }
                    }
                }
                if(count!=0&&tmp_sum<=t*count){
                    total_count++;
                }
            }
        }

        System.out.println(total_count);

    }
}

二维前缀和

原理参考：

https://blog.csdn.net/m0_65998513/article/details/132534198

import java.util.Scanner;

public class NeighborAvg {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int L = sc.nextInt();
        int r = sc.nextInt();
        int t = sc.nextInt();
        sc.nextLine();
        int[][] arr = new int[n][n];
        int[][] sum_arr = new int[n+1][n+1];
        for(int i = 0; i < n; i++){
            String line = sc.nextLine();
            String[] str_arr = line.split(" ");
            for(int j = 0; j < n; j++){
                arr[i][j] = Integer.parseInt(str_arr[j]);
                sum_arr[i+1][j+1] = sum_arr[i][j+1] + sum_arr[i+1][j]
                        - sum_arr[i][j] + arr[i][j];
            }
        }
        int total_count = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                int X1 = i-r >= 1 ? i-r : 1;
                int Y1 = j-r >= 1 ? j-r : 1;
                int X2 = i+r <= n ? i+r : n;
                int Y2 = j+r <= n ? j+r : n;
                int p = sum_arr[X2][Y2] - sum_arr[X2][Y1 -1] - sum_arr[X1-1][Y2] + sum_arr[X1-1][Y1 -1];
                if(p <= (X2- X1 + 1)*(Y2 - Y1 + 1)* t) total_count++;
            }
        }

        System.out.println(total_count);

    }
}