抓猫_KEY
抓猫
题面如下:
【 题目描述】
流浪猫布满城市的每一个角落, 非常影响市容市貌, 作为城市聘请的抓猫者, 你有一
种捕捉器, 一定可以捕捉到所有走到里面的猫, 更加幸运的是你有一个非常厉害的动物心理
学家, 他可以预测猫在不同位置的行走方向(共有东、 西、 南、 北四种情况)
为了节约经费, 问你最少需要多少个捕捉器才能把所有的猫都抓住。
【 输入格式】
输入第一行包含两个整数 N 和 M(1<=N,M<=1000),表示城市被划分成 N×M 的网格。接
下来 N 行, 每行包含 M 个字符“ E”、“ W”、“ S”、“ N” 代表东、 西、 南、 北 4 个方向, 表
示当猫在该位置的行走方向, 保证猫不会走出城市区域。
【 输出格式】
输出一个整数表示最少需要的捕捉器数。
【 样例输入输出】
D.in
3 4
SWWW
SEWN
EEEN
D.out
2
【 数据说明】
40% 1<=N,M<=4
100% 1<=N,M<=1000
【 样例说明】 捕鼠器放在( 3,4) 点和( 2,2) 点或( 2,3) 点。
这道题是一道模拟题,需要用到的技巧如下:
·枚举 ·递归(DFS)
从题意来看,这道题的题意就是求集合的数量;但在寻找集合的时候,需要进行集合的合并(※)。
我解这题只需要两个数组: 一个用来存图; 一个用作判断这块区域是否走过。
首先要解决的是如何寻找集合:
初始化[判断数组]为 TRUE,然后枚举每个点,如果没走过就 find 一遍。
如何实现集合的合并(find):
你只需要在[探索区间]的时候,遇到一个已经走过的,那么可以直接退出,且ANS 不需要加一。这是因为对于当前的集合来说,已经遇到了[另一个集合]。这时,如果继续往下走,就会走与之前集合一样的路,但这两个集合是要合并的,所以没有必要继续走下去。
code:
if(find(i,j)==)ans++; void find(int x,int y)
{
if(b[x][y]!=)
{
if(b[x][y]==cnt){ans++;return;}
else return ;
}
b[x][y]=cnt;
if(a[x][y]=='E')find(x,y+);
if(a[x][y]=='W')find(x,y-);
if(a[x][y]=='N')find(x-,y);
if(a[x][y]=='S')find(x+,y);
}
时间复杂度:O(N*M)
最新文章
- css透明设置
- sublime text 乱码生成.dump问题的解决方法
- js倒计时跳转页面
- 复制本地文件到HDFS本地测试异常
- JavaScript使用DeviceOne开发实战(四)仿优酷视频应用
- 使用虚拟按钮(Ghost Buttons)的25个网站
- JAVA中线程同步的方法(7种)汇总
- Eclipse环境下JBoss调试,解决引用的工程不被部署的问题
- linux下启动oracle服务命令
- windows设置临时环境变量path
- BZOJ 1385: [Baltic2000]Division expression
- java_eclipse_设置全局编码_utf-8_编译class指定_运行jar乱码解决_不依赖环境
- Mangos笔记
- P177 test 6-4 UVa439
- php中使用swoole实现头协议
- 列表(list) ----python
- C# EntityFramework Code First 迁移 降级 回退到空数据库
- 201771010118马昕璐《面向对象程序设计java》第八周学习总结
- 处理JavaScript异常的正确姿势
- 在windows下安装nvm并管理nodejs版本
热门文章
- SAP Cloud for Customer销售订单External Note的建模细节
- was缓存以致web.xml更改无效
- Join Resig&#39;s “Simple JavaScript Inheritance ”
- 闲来无事,用javascript写了一个简单的轨迹动画
- BZOJ2118:墨墨的等式(最短路)
- luogu P1462 通往奥格瑞玛的道路
- 2018 Multi-University Training Contest 4 Problem B. Harvest of Apples 【莫队+排列组合+逆元预处理技巧】
- POJ 3368 Frequent values 【ST表RMQ 维护区间频率最大值】
- faster-rcnn anchor_target_layer、rpn_proposal_layer、proposal_target_layer
- Spring通过注解装配Bean