题目

题意:给你一个n*m由.和#组成的矩阵,.代表可以放,#代表不可以,问在左上角(px,py)到(右下角qx,qy)这样的一个矩阵中,放下一个长度为2宽度为1的牌有多少种放法;

#include <iostream>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
const int mod=100000000;
ll max(ll a,ll b)
{return a>b?a:b;};
int min(int a,int b)
{return a<b?a:b;}; const int max_=500;
int r[max_+5][max_+5],l[max_+5][max_+5],ans[100000+5];
char f[505][505];
int q,px,py,qx,qy,n,m; void init()
{
MM(r,0);MM(l,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(f[i][j]=='.'&&f[i-1][j]=='.') l[i][j]++;
if(f[i][j]=='.'&&f[i][j-1]=='.') r[i][j]++;
r[i][j]+=r[i-1][j]+r[i][j-1]-r[i-1][j-1];
l[i][j]+=l[i-1][j]+l[i][j-1]-l[i-1][j-1];
}
} int main()
{
while(~scanf("%d %d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%s",f[i]);
for(int j=m-1;j>=0;j--)
f[i][j+1]=f[i][j];
f[i][0]='#';
}
init();
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d %d %d %d",&px,&py,&qx,&qy);
ans[i]=r[qx][qy]-r[qx][py]-r[px-1][qy]+r[px-1][py];
ans[i]+=l[qx][qy]-l[qx][py-1]-l[px][qy]+l[px][py-1];
//这个地方需要细心一点,不是单纯的和计算面积一样,需要考虑牌的放法
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
}
return 0;
}

  分析:本来还以为位是迷宫问题,后来看了题解后才发现只要处理下二维前缀就好,l,r数组分别代表

从左上角到(i,j)这个点分别按能行吗,列所能放置的种数

最新文章

  1. MySQL学习笔记十二:数据备份与恢复
  2. Spring PropertyPlaceholderConfigurer数据库配置
  3. 移动端 iframe的使用
  4. 全是套路——BFS
  5. jdk1.8 J.U.C之FutureTask实现机制分析
  6. Java并发编程:Future接口、FutureTask类
  7. android源代码百度网盘分享
  8. MegaCli 安装过程
  9. 详解react/redux的服务端渲染:页面性能与SEO
  10. Postgresql合并年月日、月份和日期左侧补零
  11. metasploit与Cobaltstrike互相派生shell
  12. BZOJ4552 HEOI2016/TJOI2016排序(线段树合并+线段树分裂)
  13. JS-1
  14. 一、selenium 环境搭建
  15. Visual Studio 2019及其注册码
  16. [转*译]Networking API Improvements in Windows 10
  17. Java中 Vector的使用详解
  18. facebook 摘要生成阅读笔记(二) Abstractive Sentence Summarization with Attentive Recurrent Neural Networks
  19. Owin WebApi版本控制
  20. 服务器安装Ubuntu的那些坑

热门文章

  1. [转帖]Java 8新特性探究(九)跟OOM:Permgen说再见吧
  2. [转帖]ORA-00600: internal error code, arguments: [4193]问题解决
  3. 小记---------破解idea2018.3.6 转载
  4. vs2019编译opencv
  5. 阿里云服务器配置https
  6. mySql 的常用命令
  7. NLP 基于kashgari和BERT实现中文命名实体识别(NER)
  8. linux下ifconfig只剩下lo的解决方法
  9. Linux操作系统的常用命令(一)
  10. Ubuntu中用sudo apt-get install makeinfo时,出错:Unable to locate package