博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
蓝桥杯-计蒜客之踏青
阅读量:7244 次
发布时间:2019-06-29

本文共 1594 字,大约阅读时间需要 5 分钟。

题干:

蒜头君和他的朋友周末相约去召唤师峡谷踏青。他们发现召唤师峡谷的地图是由一块一块格子组成的,有的格子上是草丛,有的是空地。草丛通过上下左右 4 个方向扩展其他草丛形成一片草地,任何一片草地中的格子都是草丛,并且所有格子之间都能通过上下左右连通。如果用'#'代表草丛,'.'代表空地,下面的峡谷中有 2 片草地。

1 ##..
2 ..##
处在同一个草地的 
2 个人可以相互看到,空地看不到草地里面的人。他们发现有一个朋友不见了,现在需要分头去找,每个人负责一片草地,蒜头君想知道他们至少需要多少人。

输入格式

第一行输入 nm (1n,m100) 表示峡谷大小

接下来输入 n 行字符串表示峡谷的地形

输入格式

输出至少需要多少人

样例输入

5 6.#......#.....#..#...##..#....

样例输出

5 问题分析:   这个问题其实就是问:一共有多少片草地。(自我感觉题目描述的不是很清楚) 解决方法:   使用的方法就是“深搜”。首先找到一个草丛,即‘#’,然后从该草丛处开始搜索来确定有多少草丛与该草丛直接或间接相连,搜索完毕之后得到一片草地,这片草地只需要一个人; 然后再从未被搜索过的草丛处开始搜索,即重复上述步骤,直到所有的草丛都被搜过。   注意:要区分开我所说的“草丛”和“草地”,多个相连的“草丛”连成一片草地。 代码如下:
#include
#include
using namespace std;char Map[105][105];int vis[105][105]={
0};int dir[4][2]={
{-1,0},{
1,0},{
0,-1},{
0,1}};int n,m;int cnt;void dfs(int x,int y) { vis[x][y]=1; for(int i=0;i<4;i++){ int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(xx>=1 && xx<=n && yy>=1 && yy<=m && vis[xx][yy]==0 && Map[xx][yy]=='#'){ dfs(xx,yy); } }}int main(){ while(cin>>n>>m){ cnt=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>Map[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(Map[i][j]=='#' && vis[i][j]==0){ cnt++; dfs(i,j); ///此处的深搜,每次搜索搜出来的就是一片草地,这片草地可能只有一个草丛,也可能有多个草丛 } } } cout<
<

 

转载于:https://www.cnblogs.com/ACPIE-liusiqi/p/8615090.html

你可能感兴趣的文章
overlapped编程
查看>>
HDU1027 Ignatius and the Princess II( 逆康托展开 )
查看>>
PHP函数索引-J
查看>>
Python 列表和元组
查看>>
Python 条件 循环 及其他语句
查看>>
nuxt跨域
查看>>
第六天个人总结
查看>>
Vagrant工具的安装
查看>>
JavaEE(八)
查看>>
(转载)三种主流的WebService实现方案(REST/SOAP/XML-RPC)简述及比较
查看>>
CSS3之column
查看>>
The content of element type "struts-config" must match "(display-name?,descr
查看>>
last 命令
查看>>
输出元素n的所有组合数
查看>>
java学习------异常
查看>>
Android - Activity定制横屏(landscape)显示
查看>>
JavaScript提高:005:ASP.NET使用easyUI TABS标签显示问题
查看>>
ELK
查看>>
程序员们、PD们,你敢这样在家办公吗?
查看>>
shader 例子学习
查看>>