題目描述
小z在無聊的時候總愛仰望天空，他把天空分成了N*M塊，每一塊都有若干個星星，他想知道第(x1,y1)到第（x2,y2）之間一共有多少顆星星呢？
輸入格式
一行三個整數n、m和p，n和m的含義同上文，p的含義是詢問個數
緊接著有n行，每行m個數，表示(i,j)塊有的星星數目
接下來有p行，每行四個整數x1,y1,x2,y2，表示詢問(x1,y1)到(x2,y2)的星星個數
輸出格式
一共p行，對于每一個詢問 輸出一行，表示(x1,y1)到(x2,y2)的星星個數
樣例輸入
3 3 1
1 2 3
4 5 6
7 8 9
1 1 3 3
樣例輸出
45
#include <iostream>
using namespace std;
int a[1005][1005],sum[1005][1005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,p;
cin>>n>>m>>p;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin>>a[i][j];
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
for (int i=1;i<=p;i++)
{
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
if (x1>x2) swap (x1,x2);
if (y1>y2) swap (y1,y2);
int ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/225881.html
標籤：其他