题意:给定一个n*m的网格块,如果一个块水平或垂直方向没有相邻支撑就会掉下去

有q次询问,每次会掉下去一块,问连锁反应新掉下的块数

n,m<=2e3,q<=1e5

思路:

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
#define N 2100
#define M 4100000
#define fi first
#define se second
#define MP make_pair
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int INF=1e9;
int dx[]={-,,,};
int dy[]={,,-,}; int b[N][N],n,m,s; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} int isok(int x,int y)
{
if(x>=&&x<=n&&y>=&&y<=m) return ;
return ;
} int drop(int x,int y)
{
int s1=,s2=;
if(isok(x-,y)&&b[x-][y]==) s1++;
if(isok(x+,y)&&b[x+][y]==) s1++;
if(isok(x,y-)&&b[x][y-]==) s2++;
if(isok(x,y+)&&b[x][y+]==) s2++;
if(s1>&&s2>) return ;
return ;
} void dfs(int x,int y)
{
b[x][y]=;
s++;
rep(i,,)
{
int tx=x+dx[i],ty=y+dy[i];
if(isok(tx,ty)&&b[tx][ty]==&&drop(tx,ty)) dfs(tx,ty);
}
} int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout); int cas;
scanf("%d",&cas); while(cas--)
{
n=read(),m=read();
int q=read();
rep(i,,n)
rep(j,,m) b[i][j]=;
rep(i,,q)
{
int x=read(),y=read();
s=;
if(b[x][y]==) dfs(x,y);
printf("%d\n",s);
}
} return ;
}

最新文章

  1. 《linux内核设计与实现》读书笔记第十七章
  2. Laravel 流程分析——整体概论
  3. Activiti 查询流程定义
  4. poj 2926:Requirements(最远曼哈顿距离,入门题)
  5. oracle监听服务无法打开
  6. xss 和 csrf攻击详解
  7. [你必须知道的.NET]第三十五回,判断dll是debug还是release,这是个问题
  8. SECURITY_ATTRIBUTES 设置低权限
  9. java新手笔记20 抽象类模板(letter)
  10. (转)jQuery验证控件jquery.validate.js使用说明+中文API
  11. 关于ORACLE通过file_id与block_id定位数据库对象遇到的问题的一点思考
  12. Android -- 从源码的角度一步步打造自己的TextView
  13. W3CSchool实战闯关笔记(JavaScript)
  14. 获取与esp8266连接的客户端的Mac地址 IP 端口 控制停止等问题
  15. nginx + rtmp 搭建流媒体服务器
  16. mui 轮播
  17. SharePoint 如何导出部署的场解决方案
  18. Node.js缓存
  19. UVaLive 3983 Robotruck (DP + 单调队列)
  20. SpringBoot实战(四)获取接口请求中的参数(@PathVariable,@RequestParam,@RequestBody)

热门文章

  1. 阶段1 语言基础+高级_1-3-Java语言高级_06-File类与IO流_02 递归_1_递归概念&amp;分类&amp;注意事项
  2. 疯狂Java学习
  3. Java相关面试题总结+答案(九)
  4. C#Exception 追踪异常位置
  5. 【洛谷p2239】螺旋矩阵
  6. ARM汇编3
  7. 使用内核LED框架搭建驱动 ——led_classdev_register
  8. nodejs、npm、 typescript、angular-cli安装
  9. sql 时间函数大全
  10. Java Web项目使用图形验证码 — Kaptcha