題
題意
h行w列的矩形格子，“." 代表空的，"#" 代表滿的，多米諾是 1*2 的長方體，現在放進格子，給你子矩形的左上角和右上角，問在子矩形裡共有多少種放一塊多米諾的方法。
分析
如果是空的，我們存為a[i][j]=1;滿的為0。
我們可以儲存 b[i][j] 表示前 i 行 j 列有多少種放法，遞推來求。
要求的大矩形的放法總數，就是粉色+紫色+藍色+白色和紅色框框的放法。
b[i][j-1]就是粉色+紫色，b[i-1][j]就是粉色+藍色
b[i][j] += b[i][j-1] + b[i-1][j] -b[i-1][j-1]。
如果a[i][j]==1，b[i][j] += a[i][j-1]+a[i-1][j]。
針對每個詢問：r1，c1到r2，c2 共有多少放法
ans += b[r2][c2] - b[r2][c1-1] - b[r1-1][c2] + b[r1-1][c1-1]。
接下來判斷邊界是否還有如圖中白色框框的，要減去。
r1到r2行，如果c1列為空，而c1-1列也為空，那就要減去，
c1到c2列，如果r1行為空，而r1-1行也為空，那也要減去。
代碼
#include <stdio.h>
#include <algorithm>
#define F(a,b,c) for(int a=b;a<=c;a++)
#define N 505
using namespace std;
int h,w,a[N][N],b[N][N],q,ans;
int r1,c1,r2,c2;
char ch;
int main()
{
scanf("%d%d",&h,&w);
F(i,1,h)F(j,1,w)
{
scanf(" %c",&ch);
if (ch == '.')
a[i][j]=1;
}
F(i,1,h)F(j,1,w)
{
b[i][j] = b[i][j-1] + b[i-1][j] - b[i-1][j-1];
if (a[i][j])
b[i][j] += a[i][j-1] + a[i-1][j];
}
scanf("%d",&q);
F(i,1,q)
{
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
ans = b[r2][c2] - b[r2][c1-1] - b[r1-1][c2] + b[r1-1][c1-1];
F(j,r1,r2)
if (a[j][c1] && a[j][c1-1])
ans--;
F(j,c1,c2)
if (a[r1][j] && a[r1-1][j])
ans--;
printf("%d\n",ans);
}
return 0;
} ┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆ ┆可┆有┆謙┆戮┆那┆ ┆大┆始┆ ┆然┆
┆薄┆一┆臨┆你┆的┆還┆沒┆ ┆來┆ ┆是┆來┆遜┆沒┆些┆ ┆雁┆終┆ ┆而┆
┆ ┆暖┆ ┆如┆地┆站┆有┆ ┆也┆ ┆我┆ ┆的┆有┆精┆ ┆也┆沒┆ ┆你┆
┆ ┆這┆ ┆試┆方┆在┆逃┆ ┆會┆ ┆在┆ ┆清┆來┆準┆ ┆沒┆有┆ ┆沒┆
┆ ┆生┆ ┆探┆ ┆最┆避┆ ┆在┆ ┆這┆ ┆晨┆ ┆的┆ ┆有┆來┆ ┆有┆
┆ ┆之┆ ┆般┆ ┆不┆ ┆ ┆這┆ ┆裡┆ ┆沒┆ ┆殺┆ ┆來┆ ┆ ┆來┆