【CodeForces 611C】New Year and Domino

题意

  h行w列的矩形格子,“." 代表空的,"#" 代表满的,多米诺是 1*2 的长方体,现在放进格子,给你子矩形的左上角和右上角,问在子矩形里共有多少种放一块多米诺的方法。

分析

  如果是空的,我们存为a[i][j]=1;满的为0。

  我们可以储存 b[i][j] 表示前 i 行 j 列有多少种放法,递推来求。

【CodeForces 611C】New Year and Domino

  要求的大矩形的放法总数,就是粉色+紫色+蓝色+白色和红色框框的放法。

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 共有多少放法

【CodeForces 611C】New Year and Domino

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,,h)F(j,,w)
{
scanf(" %c",&ch);
if (ch == '.')
a[i][j]=;
}
F(i,,h)F(j,,w)
{
b[i][j] = b[i][j-] + b[i-][j] - b[i-][j-];
if (a[i][j])
b[i][j] += a[i][j-] + a[i-][j];
}
scanf("%d",&q);
F(i,,q)
{
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
ans = b[r2][c2] - b[r2][c1-] - b[r1-][c2] + b[r1-][c1-];
F(j,r1,r2)
if (a[j][c1] && a[j][c1-])
ans--; F(j,c1,c2)
if (a[r1][j] && a[r1-][j])
ans--; printf("%d\n",ans);
}
return ;
}
上一篇:一次聊天引发的思考--java并发包


下一篇:[WPF]如何使用代码创建DataTemplate(或者ControlTemplate)