1242 . 午餐大反攻 Lunch Reloaded
Description
之前北市賽曾經考過一題(TIOJ 1062)，題目是這樣的:
現在有個r*c的地圖，亦即有r列、c行，每個格子有一些人在裡頭
定義一個人從某格到另一格的距離是他最少需要走幾格才能到達
定義這個午餐地點的代價為所有人從他們的位置到這格的距離和
現在要將選定某個格子作為午餐地點，試問最小的代價是多少?
這題目原本不難，不過現在由於物價上漲惹得午餐業者不爽了，他們決定把問題弄得難一點
而可憐的你，不但午餐變貴，你還要成為他們的出氣筒幫忙寫程式，寫不出來就沒午餐吃 :(
現在同樣地給你一個地圖以及上面每格有幾個人，對於每張地圖，你將要回答q個問題:
每個問題會給你一個矩形範圍
並詢問你對這個範圍內的人來說(僅考慮這個矩形內的人而不考慮其他人)，選定一個午餐地點的代價最少是多少?
Input Format
每次輸入只有一組測試資料
第一行有兩個整數r, c ，代表地圖為r列c行
接下來的r列，每列有c個整數，表示地圖上每個位置的人數
之後有個整數q, 代表接下來的詢問數量
最後q行，每行有4個整數r1,r2,c1,c2 ，代表詢問以(r1,c1)為左上角，(r2,c2)為右下角的矩形區域
1 <= r, c <= 1,000
1 <= q <= 100,000
1 <= r1 <= r2 <= r
1 <= c1 <= c2 <= c
地圖上每一格的人數都在int的範圍內。
Output Format
對於每個詢問，請在單獨一行輸出一個整數代表午餐地點的最小代價。
Sample Input 1
3 4
0 0 2 0
5 3 4 1
1 0 0 0
4
1 1 1 1
1 3 1 3
1 3 1 4
2 3 3 4
0 0 2 0
5 3 4 1
1 0 0 0
4
1 1 1 1
1 3 1 3
1 3 1 4
2 3 3 4
Sample Output 1
0
15
17
1
15
17
1
Hints
Problem Source
原TIOJ1242 / Problem Provider: DarkKnight, Description by: kelvin
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 8 |
| 2 | 1 | 8 |
| 3 | 2 | 8 |
| 4 | 3 | 8 |
| 5 | 4 | 8 |
| 6 | 5 | 8 |
| 7 | 6 | 8 |
| 8 | 7 | 8 |
| 9 | 8 | 8 |
| 10 | 9 | 8 |
| 11 | 10 | 8 |
| 12 | 11 | 12 |