UOJ #585. 新年和多米诺

【题目描述】：Limak是一只喜欢玩的小北极熊。 他最近得到了一个带有h行和w列的矩形网格。 每个单元格都是一个正方形，可以是空的（用'.'表示），也可以是禁止的（用'＃'表示）。 行从上到下编号为1到h。 列从左到右编号为1到w。此外，Limak还有一张多米诺骨牌。 他想把它放在网格中的某个地方。 多米诺骨牌将恰好占据两个相邻的单元格，位于一行或一列中。 两个相邻的单元格必须为空，并且必须位于网格内。Limak需要更多的乐趣，因此他会考虑一些问题。 在每个查询中，他选择一个矩形，并思考有多少种方法可以将一个多米诺骨牌放在所选矩形内？
【输入描述】：第一行包含两个整数h和w（1≤h,w≤500）；接下来的h行描述了一个网格。 每行包含一个长度为w的字符串。 每个字符都是'.' 或'＃'；下一行包含一个整数q（1≤q≤100000），表示查询次数；接下来的q行中的每一行包含四个整数r1i，c1i，r2i，c2i（1≤r1i≤r2i≤h，1≤c1i≤c2i≤w），表示第i个查询。 数字r1i和c1i分别表示矩形的左上单元格的行和列。 数字r2i和c2i分别表示矩形右下单元格的行和列。
【输出描述】：输出q行，每行一个正整数，表示对应询问的方案数。
【样例输入1】：5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8【样例输出1】：4
0
10
15【样例输入2】：7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8【样例输出2】：53
89
120
23
0
2【时间限制、数据范围及描述】：时间：1s 空间：256M40%的数据：1≤h,w≤100；1≤q≤10000；100%的数据：1≤h,w≤500；1≤q≤100000；本题可以算出每一行和每一列的贡献,统计答案时将这些贡献相减再相加即可.Code:
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=505;
int h,w,q,r[N][N],l[N][N],r1,c1,r2,c2;
char c[N][N];
int main(){scanf("%d%d",&h,&w);for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){cin>>c[i][j];}}for(int i=1;i<=h;i++){int tot=0;for(int j=1;j<=w;j++){if(c[i][j]=='#'){tot=0;r[i][j]=r[i][j-1];continue;}tot++;if(tot!=1){r[i][j]=r[i][j-1]+1;}else{r[i][j]=r[i][j-1];}}}for(int j=1;j<=w;j++){int tot=0;for(int i=1;i<=h;i++){if(c[i][j]=='#'){tot=0;l[i][j]=l[i-1][j];continue;}tot++;if(tot>1){l[i][j]=l[i-1][j]+1;}else{l[i][j]=l[i-1][j];}}}scanf("%d",&q);while(q--){scanf("%d%d%d%d",&r1,&c1,&r2,&c2);int ans=0;for(int i=r1;i<=r2;i++){ans+=r[i][c2]-r[i][c1];}for(int j=c1;j<=c2;j++){ans+=l[r2][j]-l[r1][j];}printf ("%d\n",ans);}return 0;
}

转载于:https://www.cnblogs.com/ukcxrtjr/p/11531253.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！