Red and Black 模板题 /// BFS oj22063
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and Hare the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
'.' --- a black tile
'#' --- a red tile
'@' --- a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
45
59
6
13
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m[][];
m[][]=-; m[][]=;
m[][]=; m[][]=;
m[][]=; m[][]=-;
m[][]=; m[][]=; /// 上下左右四种位移 int h,w,flag[][];
while(~scanf("%d%d",&h,&w)&&h&&w)
{
int a,b,sum=; char ch[][];
for(int i=;i<=w;i++)
{
getchar();
for(int j=;j<=h;j++)
{
scanf("%c",&ch[i][j]);
if(ch[i][j]=='@')
a=i,b=j; /// 记录人的位置,即起点
}
} memset(flag,,sizeof(flag));
flag[a][b]=; queue <int> x,y;
x.push(a),y.push(b);
while(!x.empty()&&!y.empty())
{
for(int i=;i<;i++)
{
a=x.front()+m[i][];
b=y.front()+m[i][];
if(a>&&a<=w&&b>&&b<=h //如果点在范围内,且
&&ch[a][b]!='#'&&!flag[a][b])//位于没走过的黑瓷砖
x.push(a), y.push(b), sum++; //放入队列 否则忽略
flag[a][b]=;
}
x.pop(), y.pop();
}
printf("%d\n",sum);
} return ;
}
最新文章
- 使用Java-UrlConnection调用webService接口
- EasyUI关于 numberbox,combobox,validatebox 的几个小问题
- nginx+lua_nginx+GraphicsMagick生成实时缩略图
- codeforces 425A Sereja and Swaps(模拟,vector,枚举区间)
- busybox配置telnetd
- NIO的Selector
- strspn和strcspn妙用
- cf D. Xenia and Hamming
- Codeforces 448 D. Multiplication Table
- PHP 7: PHP 变量和常量的定义
- 第六百二十六天 how cna I 坚持
- 番外篇--Moddule Zero介绍
- Problem : 1002 ( A + B Problem II )
- python爬虫scrapy之登录知乎
- mysql面试题分组并合并列
- [PGM] Markov Networks
- java.lang.NoClassDefFoundError: org/springframework/web/context/WebApplicationContext
- Thinkphp5笔记四:设置模板路径
- PHP随机浮点数
- [javaSE] 数据结构(栈)
热门文章
- Jmeter断言-所有断言讲解
- POJ 1873 UVA 811 The Fortified Forest (凸包 + 状态压缩枚举)
- PAT_A1067#Sort with Swap(0, i)
- flex上下、左右居中
- ThinkPHP5实用的数据库操作方法
- js关于if()else{}中的判定条件的认识,各种数据类型转换为Boolean类型的转换规则
- Pandas之read_excel()和to_excel()函数解析
- Ubuntu18.04 一键升级Python所有第三方包
- sublime里面几个个人觉得比较实用的快捷键
- C# ;获取系统开机时间