這題是二維矩陣 但想不到好方法如第一題般先建表？有高手可以提供方向嘛？

naive 的作法吃了TLE...

/////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int baozudu[500+1][500+1]= {0};

int main(int argc,char* argv[]) {
    int i=0,j=0,k=0,n=0,m=0,x1=0,y1=0,x2=0,y2=0,sum=0;

    while(scanf("%d %d",&n,&m)!=EOF) {

        memset(baozudu,0,sizeof(baozudu));

        for(i=0; i<n; ++i) {
            for(j=0; j<n; ++j) {
                scanf("%d",&baozudu[i][j]);

            }
        }

        for(k=0; k<m; ++k) {

            sum=0,x1=0,y1=0,x2=0,y2=0;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);;
            for(i=x1-1; i<=x2-1; ++i) {
                for(j=y1-1; j<=y2-1; ++j) {
                    sum+=baozudu[i][j];
                }
            }
            printf("%d\n",sum);

        }
    }

    return 0;
}

baozudu[第i行][第i行從第一個數加到第j個數的和]

//答案如下:

#include <stdio.h>

int main(){

    int m,n,i,j,x1,x2,y1,y2,a;

    while(scanf("%d%d",&n,&m)!=EOF){

        int A[n][n],B[n][n];

        for(i=0;i<n;i++){

            for(j=0;j<n;j++){

            scanf("%d",&A[i][j]);

            if(i==0&&j==0){

                B[0][0]=A[0][0];

            }

            else if(i==0){

                B[0][j]=A[0][j]+B[0][j-1];

            }

            else if(j==0){

                B[i][0]=A[i][0]+B[i-1][0];

            }

            else{

                B[i][j]=B[i-1][j]+B[i][j-1]-B[i-1][j-1]+A[i][j];

            }

            }

        }

        for(i=0;i<m;i++){

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            a=B[x2-1][y2-1];

            if(x1!=1){a-=B[x1-2][y2-1];}

            if(y1!=1){a-=B[x2-1][y1-2];}

            if(x1!=1&&y1!=1){a+=B[x1-2][y1-2];}

            printf("%d\n",a);

        }

    }

    return 0;

}

//(1,1)(1,2)(1,3)(1,4)

//(2,1)(2,2)(2,3)(2,4)

//(3,1)(3,2)(3,3)(3,4)

//(4,1)(4,2)(4,3)(4,4)

//(2,2)加到(4,4)=>>>(1,1)加到(4,4)-(1,1)加到(4,1)-(1,1)加到(1,4)+(1,1)

//用這樣解