博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
DFS深搜poj1979
阅读量:5108 次
发布时间:2019-06-13

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

深搜,从一点向各处搜找到所有能走的地方。

Red and Black
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 12004 Accepted: 6097

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.

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.

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

4559613
#include
using namespace std; char map[22][22]; int sum,l,h; int dir[4][2]={
{
1,0},{
-1,0},{
0,1},{
0,-1}}; bool border(int x,int y) {
if(x<0||x>=h||y<0||y>=l) return 0; return 1; } void search(int x,int y) {
int i; int xx,yy; sum++; map[x][y]='#'; for(i=0;i<4;i++) {
xx=x+dir[i][0]; yy=y+dir[i][1]; if(border(xx,yy)&&map[xx][yy]=='.') search(xx,yy); } } int main() {
int i,j; int x0,y0; while(cin>>l>>h) {
sum=0; if(l==0&&h==0)break; for(i=0;i
>map[i][j]; if(map[i][j]=='@') {
x0=i; y0=j; } } } search(x0,y0); cout<
<

转载于:https://www.cnblogs.com/qyaizs/archive/2011/07/20/2111246.html

你可能感兴趣的文章
遇到的Mysql的一个坑
查看>>
AC日记——「HNOI2017」单旋 LiBreOJ 2018
查看>>
vue总结
查看>>
真机调试的准备工作介绍
查看>>
(笔记)Linux内核学习(十一)之I/O层和I/O调度机制
查看>>
[lintcode medium] Delete digits
查看>>
3.29下午
查看>>
macOS升级到high Sierra后, Cocoapods不能使用解决办法
查看>>
vmstat详细说明
查看>>
php类点滴---访问修饰符public protected private
查看>>
spring-boot的helloWorld详解
查看>>
Codeforces 919 A. Supermarket
查看>>
NYOJ 21.三个水杯-初始态到目标态的最少次数-经典BFS
查看>>
实验四+164+张增进
查看>>
第09次:升级《陋习手记》滑动和对话框
查看>>
url传参(所传的参数为数字,汉字。获取该参数为汉字乱码)
查看>>
简单了解下CGI、FastCGI和php-fpm的概念和区别和运行原理
查看>>
TIME_WAIT 太多的解决办法[转载]
查看>>
低版本中使用高版本出现的类怎么办?
查看>>
GlusterFS性能测试
查看>>