2806 红与黑 个人博客:doubleq.win

个人博客:doubleq.win

2806 红与黑

 时间限制: 1 s

 空间限制: 64000 KB

 题目等级 : 白银 Silver

题解

 查看运行结果

题目描述 Description

有一个矩形房间,覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上,由此出发,可以移到四个相邻瓷砖之一,但他不能移动到红砖上,只能移动到黑砖上。编写一个程序,计算他通过重复上述移动所能经过的黑砖数。

输入描述 Input Description

输入包含多个数据集。一个数据集开头行包含两个正整数W和H,W和H分别表示矩形房间的列数和行数,且都不超过20. 每个数据集有H行,其中每行包含W个字符。每个字符的含义如下所示: '.'——黑砖 '#'——红砖 '@'——男子(每个数据集仅出现一次) 两个0表示输入结束。

输出描述 Output Description

对每个数据集,程序应该输出一行,包含男子从初始瓷砖出发可到达的瓷砖数。

样例输入 Sample Input

6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0

样例输出 Sample Output

45 59 6 13

数据范围及提示 Data Size & Hint

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int a[101][101];
 6 int x,y;
 7 int xx[9]={-1,+1,0,0};
 8 int yy[9]={0,0,-1,+1};
 9 int tot;
10 int vis[101][101];
11 void dfs(int x,int y)
12 {
13     for(int i=0;i<4;i++)
14     {
15         if(a[x+xx[i]][y+yy[i]]==1&&vis[x+xx[i]][y+yy[i]]==0)
16         {
17             vis[x+xx[i]][y+yy[i]]=1;
18             tot++;
19             dfs(x+xx[i],y+yy[i]);
20         }
21     }
22 }
23 int main()
24 {
25     int n,m;
26     while(1)
27     {    
28     cin>>m>>n;
29     if(m==0&&n==0)
30     break;
31     tot=0;
32     memset(vis,0,sizeof(vis));
33     memset(a,0,sizeof(a));
34     for(int i=1;i<=n;i++)
35     {
36         for(int j=1;j<=m;j++)
37         {
38             char p;
39             cin>>p;
40             if(p=='@')
41             {
42                 x=i;
43                 y=j;//初始位置 
44             }    
45             else if(p=='.')
46             a[i][j]=1;//黑砖 可以行走
47             else if(p=='#')
48             a[i][j]=0;//红砖 不可以行走 
49             else continue;
50         }
51     }
52     dfs(x,y);
53     cout<<tot+1<<endl;
54     }
55     return 0;
56 }

最简单最暴力的搜索

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习入门

POJ 刷题系列:2965. The Pilots Brothers' refrigerator

POJ 刷题系列:2965. The Pilots Brothers’ refrigerator 传送门:POJ 2965. The Pilots Brothe...

20760
来自专栏owent

HDU HDOJ 3398 String 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3398

8030
来自专栏后端技术探索

(答案来了)两道腾讯面试题目

前天推送的文章《两道腾讯技术面试题(二面经历)》,收到了不少留言,感兴趣的可以去哪篇文章下查看精选留言,有一多半同学没有正确理解题目,可分享的留言寥寥无几,根据...

11910
来自专栏计算机视觉与深度学习基础

Leetcode 239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from t...

21650
来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

16600
来自专栏数据小魔方

字符串提取函数

今天要跟大家分享三个excel中使用频率最高的字符串提取函数——left/right/mid函数。 ▽▼▽ 这三个函数分别对用截取某一单元格文本的左、右、中间某...

36550
来自专栏算法channel

Tensorflow|通过Variable及assign()感悟一点设计之道

01 Variable a = tf.Variable(2, name="scalar") # create variable a with scalar v...

2.1K70
来自专栏机器学习算法与Python学习

Numpy

Numpy Numpy是Python中用于科学计算的核心库。它提供了高性能的多维数组对象,以及相关工具。(本文文末的原文链接为numpy的官方文档) NumPy...

35070
来自专栏数据结构与算法

1265. [NOIP2012] 同余方程

1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

34560
来自专栏逸鹏说道

小白眼中的AI之~Numpy基础

引入一下 Numpy模块, Numpy的数组使用可以查看一下帮助文档, Numpy的 array数组类型必须是一致的(后面会讲)

11340

扫码关注云+社区

领取腾讯云代金券