ZOJ 1047 Image Perimeters(BFS搜索)_Yuki_fx的博客-程序员宅基地

技术标签: 搜索  

题目比较长,题目中给你解释了一个样例。
我大概说一下题目的意思,题目给你一个地图,包含字符X和.。
给你一个起点,让你从8个方向去搜索,找X连通块的周长。

如果还没太理解,可以看下题目中图二的例子,题目给定的起点就是2,3;
从这个起点出发,往8个方向扩展以后得到的连通块就是图中圈出来的部分。
这一部分的周长数一数,可以数出来是18。


这一道题目的数据范围比较小,行和列只有20.可以用搜索做。
这里我用的是广度优先搜索BFS。
处理周长的方法:当以一个点为出发点出发时,搜索8个方向,如果这8个方向中的
上 左 下 右这四个方向有一个方向没有X,周长就加1

这样处理下来得到的就是答案

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<queue>
using namespace std;
int n,m,s,e,sum;
char maps[200][200];
int vis[200][200];
int next[8][2]={-1,0,0,-1,1,0,0,1,-1,-1,1,-1,1,1,-1,1};//方向数组
//上 左 下 右 左上 左下 右下  右上
struct node
{
	int x,y;
}k,tmp;
queue<node> que;

void bfs()
{
	int x,y,i;
	while(que.size())
	{
		k=que.front();
		que.pop();
		for(i=0;i<8;i++)
		{
			x=k.x+next[i][0]; y=k.y+next[i][1];
			if(maps[x][y]=='X'&&!vis[x][y])
			{
				tmp.x=x;	tmp.y=y;
				vis[x][y]=1;

				que.push(tmp);
			}
			else if(i<=3&&maps[x][y]!='X')//上左下右四个方向
				sum++;
		}
	}
}
int main()
{
	int i,j;
	while(scanf("%d%d%d%d",&n,&m,&s,&e)!=EOF)
	{
		sum=0;
		memset(maps,0,sizeof(maps));
		memset(vis,0,sizeof(vis));//清空标记
		getchar();
		if(n==0&&m==0&&s==0&&e==0)
			break;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
				scanf("%c",&maps[i][j]);
			getchar();
		}
		tmp.x=s; tmp.y=e;
		vis[s][e]=1;
		que.push(tmp);
		bfs();
		printf("%d\n",sum);
	}
	return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Yuki_fx/article/details/77225942

智能推荐

RedisPool操作Redis,工具类实例_乐事原味~的博客-程序员宅基地_redis.pool.maxactive

redis.properties配置文件内容redis.pool.maxActive=100redis.pool.maxIdle=20redis.pool.maxWait=3000redis.pool.testOnBorrow=falseredis.pool.testOnReturn=falseredis.ip=127.0.0.1redis.port=6379redis.po...

三门问题_hustmba99的博客-程序员宅基地

三门问题(问题来源于Crossin的编程教室)三门问题(Monty Hall problem)亦称为蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论,大致出自美国的电视游戏节目 Let's Make a Deal。问题名字来自该节目的主持人蒙提·霍尔(Monty Hall)。参赛者会看见三扇关闭了的门,其中一扇的后面有一辆汽车,选中后面有车的那扇门可赢得该汽车,另外两扇门后面则各藏有一只山羊。当参赛者选定了一

java并发多线程-返回执行结果(Callable和Future)(9)_fangqun663775的博客-程序员宅基地

启动一个线程不论使用Thread或者Runnable的时候,都是没有返回结果的。也就是说Thread和Runnable的run()方法必须没有返回值。   public void run(){} 解决方案: Callable和Future,一个产生结果,一个拿到结果。 简单的来一个实例demo帮助我们理解:

AF_INET 和 PF_INET_The_Big_Sun的博客-程序员宅基地_af_inet pf_inet

AF 表示ADDRESS FAMILY 地址族 PF 表示PROTOCL FAMILY 协议族但这两个宏定义是一样的所以使用哪个都没有关系Winsock2.h中#define AF_INET 0#define PF_INET AF_INET所以在windows中AF_INET与PF_INET完全一样而在Unix/Linux系统中,

MySQL修改默认事务隔离级别_forever_together的博客-程序员宅基地_mysql 修改默认隔离级别

一、查看当前 MySQL 版本号select version();二、查看当前全局事务隔离级别1、MySQL5.6 及其更早的版本select @@global.tx_isolation;2、MySQL5.7 及更高版本select @@global.transaction_isolation;1、MySQL5.7 引入了 transaction_isolation 用来代替 tx_isolation,并在 MySQL8.0.3 去掉了 tx_isolation,在 .

随便推点

【cpufreq】【core】_money_yuan的博客-程序员宅基地

cpufreq子系统中,核心层会为driver和governor提供一系列的接口一、cpufreq_register_driver其中由cpufreq core完成的是注册和注销函数/********************************************************************* * REGISTER / U...

有关软件测试的问答(转)_张兆军的博客-程序员宅基地

1、对于新产品和维护版的老产品设计的用例应该注意些什么呢?  专家分析:新项目和维护项目从本质上看没有区别,维护产品,无非就是新增功能和缺陷修复两大类,和新项目相比,唯一需要注意的就是新增\修复的功能是否对其他部分有影响,这里就涉及到一个回归策略的问题——老功能要测多少。一般来说,需要和开发讨论确定受影响的范围,然后制定测试范围。当然最理想的情况就是整个系统全测,因为一旦系统复杂了,没有哪

wordpress访问加速_ganland的博客-程序员宅基地

<br />WordPress加速及优化的13个技巧<br />维护和加速WordPress的必备技巧<br />    给WordPress博客加速<br /> 用.htaccess缓存图片,提高博客运行效率<br /> <br />WORDPRESS程序SEO优化方法大总结

java几个常见的基础错误_aik22864的博客-程序员宅基地

1.String 相等稍微有点经验的程序员都会用equals比较而不是用 ==,但用equals就真的安全了吗,看下面的代码user.getName().equals("xiaoming");有经验的老司机很快就能看到问题,如果user.getName()为null,就会抛出空指针异常,因此下面的写法更为稳妥"xiaoming".equals(us...

Keras:Shape函数_子綦的博客-程序员宅基地

Shapekeras.backend.shape(x)返回张量或变量的符号尺寸。参数x: 张量或变量。返回符号尺寸(它本身就是张量)。例子:# TensorFlow 例子&gt;&gt;&gt; from keras import backend as K&gt;&gt;&gt; tf_session = K.get_session()&gt;&gt;...

关于是否 禁用VMware的vmem文件_hejian1106的博客-程序员宅基地

网上 有很多 关于是否要 禁用VMware的vmem文件的帖子,总的来讲 有些帖子的年份比较早那个时候的电脑配置现在的的配置不能同日而语,所以个人觉得那个时候可行的方案现在不一定 还是最佳方案,简单来讲禁用VMware的vmem文件就是不用虚拟内存  因为虚拟内存的访问速度 不如物理内存来的快,在现在一般的机器内存多是4G 8G的情况下 禁用虚拟内存 还是能在一定程度上提升虚拟机运行速度的

推荐文章

热门文章

相关标签