1991 . 冰塊盒
TopCoder
Tags
Description
愛吃冰塊的大陸人喜歡收藏歷史悠久的冰塊。
某天大陸人網購了一塊$1 \times 2$的清朝冰塊，開心的準備放入他的收藏盒。然而，一打開盒子他就遇到了一個難題，就是他不知道要放哪個位置比較合適，尤其是收藏盒中已經有許多奇形怪狀的冰塊，讓這個問題更複雜了。
具有預知能力的大陸人算準了你現在面前有一台電腦，所以請(ㄨㄟ)求(ㄒㄧㄝˊ)你幫他算出指定範圍內，他有幾種放冰塊的方式。
注意，冰塊可以旋轉！（當然，只能放直的或橫的，不能放斜的）
Input Format
第一行包含兩個正整數$R, C$，表示冰塊盒的大小。
接著有$R$行，每行有$C$個數字，$1$表示該格是空的、$0$表示該格上有冰塊。
再來有一個正整數$Q$，表示詢問的數量。
最後有$Q$行，每行有四個整數$r_1 , c_1 , r_2 , c_2$（其中$1 \leq r_1 \leq r_2 \leq R; 1 \leq c_1 \leq c_2 \leq C$），表示詢問的範圍。
對於所有測資，$R \times C \leq 10^ 6; Q\leq 10^ 6$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $R=1$ | 35 |
| 2 (5~9) | $R \times C \leq 10^ 4$、$Q \leq 10^ 3$ | 14 |
| 3 (5~19) | $Q \leq 10^ 4$ | 24 |
| 4 (0~24) | 無 | 27 |
Output Format
針對每筆詢問，輸出冰塊放置的方法數。
Sample Input 1
7 7
1 1 1 0 1 1 1
0 1 0 0 0 1 0
0 1 0 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 0 1 0 0 1 0
1 1 1 0 1 1 0
2
1 1 3 3
5 1 7 7
1 1 1 0 1 1 1
0 1 0 0 0 1 0
0 1 0 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 0 1 0 0 1 0
1 1 1 0 1 1 0
2
1 1 3 3
5 1 7 7
Sample Output 1
4
13
13
Hints
Sample Input 第一筆詢問(1 1 3 3)的4種放法 : ( "@@" 為放置的冰塊)
| @ | @ | 1 | 1 | @ | @ | 1 | @ | 1 | 1 | 1 | 1 | ||||
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | @ | 0 | 0 | @ | 0 | ||||
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | @ | 0 |
Problem Source
Problem Set by Ting.H
建國中學106學年度校隊選拔：初試pB
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 35 |
| 2 | 5~9 | 14 |
| 3 | 5~19 | 24 |
| 4 | 0~24 | 27 |