a694: 吞食天地二

內容

好餓歐歐歐歐

有 n * n 個食物在你面前排成一個方陣

每個食物有它的飽足度

你想知道把其中一塊通通吃掉會獲得多少飽足度

輸入

多組測資以 EOF 結束

每組測資開始有兩個正整數 n,m (n<=500, m<=100000)

接下來 n 行有 n 個不超過 100 的正整數依序代表每個食物的飽足度

接下來 m 行每行有四個數字 x1,y1,x2,y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n)

代表你想要吃掉食物的範圍

3 3
1 2 3
4 5 6
7 8 9
1 1 3 3
1 1 1 3
1 1 3 1

輸出

對每組測資輸出 m 行，代表總飽足度

45
6
12

解題思路

吞食天地 的加強版，從一維變成二維，但解題邏輯一樣是建立總飽足度陣列之後用數學去取得目標區間。

建立總飽足度的二維陣列

總飽讀度計算流程(sum 為總飽足度矩陣)：

. . . .
. . . .
. . s .  如果要計算 s 點
. . . .

1 1 . .
1 1 . .
1 1 0 .   + 先加上 sum[s.X - 1][s.Y]
. . . .    (數字為該區域飽足度被計算到的次數)

2 2 1 .
2 2 1 .
1 1 0 .  再加上 sum[s.X][s.Y - 1]
. . . .    (這時候由於 2 的區域飽足感被重複加了兩次，所以待會要減掉)

1 1 1 .
1 1 1 .
1 1 0 .  減到 sum[s.X -1][s.Y - 1]
. . . .

1 1 1 .
1 1 1 .
1 1 1 .  最後加上 s點本身的飽足感即可。
. . . .

觀察上面流程得到以下公式

sum[s.X][s.y] = sum[s.X - 1][s.y] + sum[s.X][s.y - 1] - sum[s.X - 1][s.y - 1] + s 點的飽足感

取得 s 點到 e 點的區域飽足度

計算流程範例 :

 . . . . .
 . s 0 0 .
 . 0 0 0 .  如果要計算 s 到 e 區域的的飽足度
 . 0 0 e .       (也就是 s + e + 0 區域)
 . . . . .

 1 1 1 1 .
 1 1 1 1 .
 1 1 1 1 .  先加上 sum[e.X][e.Y] 點的飽足度
 1 1 1 1 .
 . . . . .

 0 1 1 1 .
 0 1 1 1 .
 0 1 1 1 .  減掉 sum[e.X][s.Y - 1] 點的飽足度
 0 1 1 1 .
 . . . . .

-1 0 0 0 .
 0 1 1 1 .
 0 1 1 1 .  減掉 sum[s.X - 1][e.Y] 點的飽足度
 0 1 1 1 .
 . . . . .

 0 0 0 0 .
 0 1 1 1 .
 0 1 1 1 .  加上 sum[s.X - 1][s.Y - 1] 點的飽足度，就會得到目標區域
 0 1 1 1 .
 . . . . .

觀察上面流程得到以下公式

s 到 e 點的總飽和度 = sum[e.X][e.y] - sum[e.X][s.y - 1] - sum[s.X - 1][e.y] + sum[s.X - 1][s.y - 1]

計算後輸出答案即可。

完整程式碼

AC (68ms, 728KB)

#include <stdio.h>

int sum[510][510];

int main()
{
    int n, m, sX, sY, eX, eY;
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                scanf(" %d", &sum[i][j]);
                sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            }
        }
        for (int i = 0; i < m; i++)
        {
            scanf("%d %d %d %d", &sX, &sY, &eX, &eY);
            printf("%d\n", sum[eX][eY] - sum[eX][sY - 1] - sum[sX - 1][eY] + sum[sX - 1][sY - 1]);
        }
    }
    return 0;
}