POJ 1979:Red and Black
2024-09-07 04:56:49
Red and Black
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 26058 | Accepted: 14139 |
Description
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.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are 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.
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.
Output
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).
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13
给一张图,@为起始点,'.'能走,‘#’不能走,问一共能走到多少'.'。
在深夜能做到这种水题也真是很令人高兴的事情。
深度搜索水题。
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; int row,col,sum;
char value[30][30];
int flag[30][30]; void dfs(int x,int y)
{
flag[x][y]=1; if(x>1&&flag[x-1][y]==0&&value[x-1][y]=='.')
{
dfs(x-1,y);
}
if(y>1&&flag[x][y-1]==0&&value[x][y-1]=='.')
{
dfs(x,y-1);
}
if(x<row&&flag[x+1][y]==0&&value[x+1][y]=='.')
{
dfs(x+1,y);
}
if(y<col&&flag[x][y+1]==0&&value[x][y+1]=='.')
{
dfs(x,y+1);
}
} void solve1()
{
int i,j;
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
if(value[i][j]=='@')
{
dfs(i,j);
return;
}
}
}
} void solve2()
{
int i,j;
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
if(flag[i][j])
{
sum++;
}
}
}
} int main()
{
int i,j;
while(cin>>col>>row)
{
if(col+row==0)
break;
memset(flag,0,sizeof(flag));
sum=0;
for(i=1;i<=row;i++)
{
cin>>value[i]+1;
}
solve1();
solve2(); cout<<sum<<endl;
} return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- ABP文档 - Javascript Api - Message
- hadoop常见问题汇集
- UOJ52——【UR #4】元旦激光炮
- 正则匹配<;{$vcode}>;变量
- Laravel 5 基础(二)- 路由、控制器和视图简介
- 团体程序设计天梯赛-练习集L1-018. 大笨钟
- leetCode 70.Climbing Stairs (爬楼梯) 解题思路和方法
- 利用c语言做简单的迷宫小游戏
- C语言经典程序190例
- 201521123078《Java程序设计》第2周学习总结
- python_crawler,批量下载文件
- 是时候选择一款富文本编辑器了(wangEditor)
- jQuery使用(十五):when()方法的使用
- EntityFrameworkCore将数据库Timestamp类型在程序中转为long类型
- java程序初体验
- node基础—概述与安装
- hdu-2222(ac自动机模板)
- [原]Jenkins(一)---我理解的jenkins是这样的(附全套PDF下载)
- xml 和 json 序列化忽略字段
- 整数转罗马数字以及罗马数字转整数(java实现)
热门文章
- 吴裕雄 Bootstrap 前端框架开发——Bootstrap 字体图标(Glyphicons):glyphicon glyphicon-envelope
- 一个有意思的html验证码: namesilo验证码
- Q 格式使用总结
- CodeForces - 862B Mahmoud and Ehab and the bipartiteness(二分图染色)
- HihoCoder第七周:完全背包问题
- Spark 资源调度包 stage 类解析
- 对于python 3.x与python2.x中新型类的继承特性总结
- 每天一点点之 taro 框架开发 - taro静态资源引入
- 关于boostrap的TAB切换 ,如何获取?
- 驰骋BPM系统-表单引擎-流程引擎 2020年大换装