TTTTTTTTTTTTT CF Good Bye 2015 C- New Year and Domino(CF611C) 二维前缀
2024-10-07 02:49:46
题意:给你一个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)这个点分别按能行吗,列所能放置的种数
最新文章
- MySQL学习笔记十二:数据备份与恢复
- Spring PropertyPlaceholderConfigurer数据库配置
- 移动端 iframe的使用
- 全是套路——BFS
- jdk1.8 J.U.C之FutureTask实现机制分析
- Java并发编程:Future接口、FutureTask类
- android源代码百度网盘分享
- MegaCli 安装过程
- 详解react/redux的服务端渲染:页面性能与SEO
- Postgresql合并年月日、月份和日期左侧补零
- metasploit与Cobaltstrike互相派生shell
- BZOJ4552 HEOI2016/TJOI2016排序(线段树合并+线段树分裂)
- JS-1
- 一、selenium 环境搭建
- Visual Studio 2019及其注册码
- [转*译]Networking API Improvements in Windows 10
- Java中 Vector的使用详解
- facebook 摘要生成阅读笔记(二) Abstractive Sentence Summarization with Attentive Recurrent Neural Networks
- Owin WebApi版本控制
- 服务器安装Ubuntu的那些坑
热门文章
- [转帖]Java 8新特性探究(九)跟OOM:Permgen说再见吧
- [转帖]ORA-00600: internal error code, arguments: [4193]问题解决
- 小记---------破解idea2018.3.6 转载
- vs2019编译opencv
- 阿里云服务器配置https
- mySql 的常用命令
- NLP 基于kashgari和BERT实现中文命名实体识别(NER)
- linux下ifconfig只剩下lo的解决方法
- Linux操作系统的常用命令(一)
- Ubuntu中用sudo apt-get install makeinfo时,出错:Unable to locate package