Red and Black(杭电oj1312)(BFS)

Red and Black

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 10122    Accepted Submission(s): 6313

Problem 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)

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
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#[email protected]#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
[email protected]
###.###
..#.#..
..#.#..
0 0

Sample Output

45
59
6
13

Source

Asia 2004, Ehime (Japan), Japan Domestic

#include<stdio.h>
char s[25][25];
int a[4]={0,0,1,-1};
int b[4]={1,-1,0,0};
int m,n,sum;
void bfs(int x,int y)
{
	int k,v,t;
    s[x][y]='#';
	for(k=0;k<4;k++)
	{
		v=x+a[k];
		t=y+b[k];
		if(s[v][t]=='.'&&v>=1&&v<=n&&t>=0&&t<m)
		{
			bfs(v,t);
			sum++;
		}
	}
}
int main()
{
	int i,j;
	while(scanf("%d%d",&m,&n)&&(m+n))
	{
		for(i=1;i<=n;i++)
		scanf("%s",s[i]);
		for(i=1,sum=1;i<=n;i++)
		{
			for(j=0;j<m;j++)
			{
			   if(s[i][j]=='@')
			   bfs(i,j);
		    }
		}
		printf("%d\n",sum);
	}
	return 0;
}
时间: 11-22

Red and Black(杭电oj1312)(BFS)的相关文章

杭电ACM分类

杭电ACM分类: 1001 整数求和 水题1002 C语言实验题——两个数比较 水题1003 1.2.3.4.5... 简单题1004 渊子赛马 排序+贪心的方法归并1005 Hero In Maze 广度搜索1006 Redraiment猜想 数论:容斥定理1007 童年生活二三事 递推题1008 University 简单hash1009 目标柏林 简单模拟题1010 Rails 模拟题(堆栈)1011 Box of Bricks 简单题1012 IMMEDIATE DECODABILITY

【转】对于杭电OJ题目的分类

[好像博客园不能直接转载,所以我复制过来了..] 1001 整数求和 水题1002 C语言实验题——两个数比较 水题1003 1.2.3.4.5... 简单题1004 渊子赛马 排序+贪心的方法归并1005 Hero In Maze 广度搜索1006 Redraiment猜想 数论:容斥定理1007 童年生活二三事 递推题1008 University 简单hash1009 目标柏林 简单模拟题1010 Rails 模拟题(堆栈)1011 Box of Bricks 简单题1012 IMMEDI

杭电 1242 Rescue(广搜)

http://acm.hdu.edu.cn/showproblem.php?pid=1242 Rescue Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 15597    Accepted Submission(s): 5663 Problem Description Angel was caught by the MOLIGPY!

杭电1253 胜利大逃亡

胜利大逃亡 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 24756    Accepted Submission(s): 9478 Problem Description Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会. 魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的

HDU 4975 (杭电多校 #10 1005题)A simple Gaussian elimination problem.(网络流之最大流)

题目地址:HDU 4975 对这题简直无语...本来以为这题要用什么更先进的方法,结果还是老方法,这么卡时间真的好吗....比赛的时候用了判环的方法,一直TLE..后来换了矩阵DP的方式,加了加剪枝就过了..无语了.. 代码如下: #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cstdio> #include <

HDU 4888 (杭电多校#3)Redraw Beautiful Drawings(网络流之最大流)

题目地址:HDU 4888 自己之所以弱真心是态度的问题,以后不能再偷懒了!!那次这个题一直没补,结果这次又遇到了..还有这次遇到的最小割权闭合问题,也一直没刷,所以这次遇到了也不会,连是最小割都不知道!!(突然想起来前面还有好多题拖到现在也没做...T U T)以后绝不能再拖拉了! 这题的建图是很容易的,主要是判断唯一性不好判断.这里是用的dfs找环来判断是否唯一,因为假如有环的话,说明环 中的数字是可以相互流动而且可以保证解依然正确.. 代码如下: #include <cstdio> #i

杭电 HDU 1164 Eddy&#39;s research I

Eddy's research I Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7117    Accepted Submission(s): 4268 Problem Description Eddy's interest is very extensive, recently  he is interested in prime

hdu 1016 Prime Ring Problem DFS解法 纪念我在杭电的第一百题

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 29577    Accepted Submission(s): 13188 Problem Description A ring is compose of n circles as shown in diagram. Put natural num

一个人的旅行 HDU杭电2066【dijkstra算法】

http://acm.hdu.edu.cn/showproblem.php?pid=2066 Problem Description 虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景--草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女--眼看寒假就快到了,这么一大段时间,可不