AcWing 796. 子矩阵的和_Java    原题链接    简单

作者： 作者的头像   zning ,  2019-09-20 12:34:22 ,  所有人可见 ,  阅读 3440

26


24

二维数组求解前缀项和

求解s[i][j]
如图

求S[i][j].png

求解前缀项和
如图

前缀和.png

题目 796

代码
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // 输入值进行初始化
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        // 初始化 arr
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                arr[i][j] = in.nextInt();
//         输出查看 arr
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++)
//                System.out.print(arr[i][j] + "  ");
//        }

        // 求解 s[i][j]
        int[][] s = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                // 计算, 结合图来理解
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];

        // 循环输出
        while (q-- > 0) {
            // 定位获取区间大小
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();

            // 计算, 结合图来理解
            int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            System.out.println(res);
        }
    }
}

10 评论

用户头像
NN_   2022-10-17 12:06         踩      回复

图很清楚orz

用户头像
捧束花等你   2021-08-24 14:35         踩      回复

for(int i=1;i<=n;i++) {

        for(int j=1;j<=m;j++) {
            a[i][j]=in.nextInt();

            s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
        }
    }

这样可以只要一个for循环

用户头像
acw_zyx   2021-01-20 10:17         踩      回复

图很NB

用户头像
ballyang   2020-10-30 07:54         踩      回复

大佬 学习了

用户头像
ylimhs   2020-10-18 11:19         踩      回复

图很NB

用户头像
ac_ht6   2020-05-21 17:00         踩      回复

图很漂亮！

用户头像
._2   2019-10-22 22:14         踩      回复

大佬 用你的代码超时了 可以再看看不？ 我写的java也是AC不了

用户头像
小呆呆   2019-10-25 20:32         踩      回复 
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
import java.io.*;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str = reader.readLine().split(" ");
        int row = Integer.parseInt(str[0]);
        int col = Integer.parseInt(str[1]);
        int n = Integer.parseInt(str[2]);
        int[][] matrix = new int[row][col];
        for(int i = 0; i < row; i++){
            String[] str1 = reader.readLine().split(" ");
            for(int j = 0; j < col; j++){
                matrix[i][j] = Integer.parseInt(str1[j]);
            }
        }
        int[][] sum = new int[row + 1][col + 1];
        for(int i = 1; i < row + 1; i++){
            for(int j = 1; j < col + 1; j++){
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        for(int i = 0; i < n; i++){
            String[] str2 = reader.readLine().split(" ");
            int row1 = Integer.parseInt(str2[0]);
            int col1 = Integer.parseInt(str2[1]);
            int row2 = Integer.parseInt(str2[2]);
            int col2 = Integer.parseInt(str2[3]);
            System.out.println(sum[row2][col2] - sum[row1 -1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1]);
        }
    }
}
用户头像
小呆呆   2019-10-25 20:32         踩      回复

来自 zrjkcsd 的

用户头像
._2   2019-10-26 18:57    回复了 小呆呆 的评论         踩      回复

谢谢啦 orz