HDU 1312 统计有多少个点

Red and Black

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

Total Submission(s): 10858    Accepted Submission(s): 6797

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

题意:一幅地图,#不能走,@代表进去的点,问你有多少个点(.),@也算一个。

比较水的一道搜索题。

我写了两种代码。

BFS和DFS

#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char map[33][33];
int vis[33][33];
int n,m;
int sum;
struct node
{
	int x,y;
}
f[333];
#define inf 0xfffffff
void bfs(int x,int y)
{
	int i;
	queue<node>q;
	node st,ed;
	st.x=x;
	st.y=y;
	q.push(st);
	while(!q.empty())
	{
		st=q.front();
		q.pop();
		for(i=0;i<4;i++)
		{
			ed.x=st.x+dir[i][0];
			ed.y=st.y+dir[i][1];
			if(ed.x>=n ||ed.y>=m ||ed.x<0 ||ed.y<0 ||map[ed.x][ed.y]=='#' ||map[ed.x][ed.y]=='@')
				continue;
			map[ed.x][ed.y]='@';
			sum++;
			q.push(ed);
		}
	}
}
int main()
{
	int i,j,x,y;
	while(scanf("%d%d",&m,&n)!=EOF&&n!=0 &&m!=0)
	{
		for(i=0;i<n;i++)
			scanf("%s",map[i]);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			{
				if(map[i][j]=='@')
				{
					x=i;
					y=j;
				}
			}
			sum=1;
			bfs(x,y);
			printf("%d\n",sum);
	}
	return 0;
}
//广搜

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char map[33][33];
int vis[33][33];
int n,m;
int sum;
#define inf 0xfffffff
void dfs(int x,int y)
{
    int sx,sy,i;
    sum++;
    for(i=0;i<4;i++)
    {
        sx=x+dir[i][0];
        sy=y+dir[i][1];
        if(sx>=n ||sy>=m ||sx<0 ||sy<0 ||map[sx][sy]=='#' ||map[sx][sy]=='@')
            continue;
          map[sx][sy]='@';
              dfs(sx,sy);
    }
}
int main()
{
    int i,j,x,y;
    while(scanf("%d%d",&m,&n)!=EOF&&n!=0 &&m!=0)
    {
        for(i=0;i<n;i++)
            scanf("%s",map[i]);
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            {
                if(map[i][j]=='@')
                {
                    x=i;
                    y=j;
                }
            }
            sum=0;
            dfs(x,y);
            printf("%d\n",sum);
    }
    return 0;
}
//深搜
//深搜和广搜都是只能讲满足的点放入继续搜索,所以搜过的点要把它变成不满足的点,满足的点可以继续再搜。这就是本题的关键
时间: 01-28

HDU 1312 统计有多少个点的相关文章

HDU 1251 统计难题 Trie题解

基本上是标准的寻找前缀的问题,只需要insert和search函数就可以了. 我这里主要是修改一下n的记录方法,这里的n代表的不是叶子节点的标志,而是有多少单词经过了这条路径的标志. 然后是查找需要查找的前缀单词,如果没有找到,就返回0,表示没有单词以这个前缀单词为前缀,如果找到,直接返回n就是答案了.因为有n个单词经过了这条路径. 查找效率是常数. 使用静态分配空间的办法. #include <stdio.h> #include <string.h> const int MAX_

hdu 1312 DFS算法简单题

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=1312 此题与油田那题很像是练习深搜的好题,题意是从"@"开始,遍历整个图,找到连接的 "."有多少个 但要考虑变化,简单处理下就行了,主要是斜角的不要了,而且判断结束方式也不一样 具体看代码吧 ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

HDU 1312 ----- Red and Black 入门搜索 DFS解法

HDU 1312 ----- Red and Black  入门搜索  http://acm.hdu.edu.cn/showproblem.php?pid=1312 /*HDU 1312 ----- Red and Black 入门搜索 */ #include <cstdio> int n, m; //n行m列 int cnt, startx, starty; char mapp[25][25]; /*找一个连通的区域里可以走的块*/ void dfs(int x, int y){ if (x

HDU 1312 Red and Black (搜索)

Red and Black Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9795    Accepted Submission(s): 6103 Problem Description There is a rectangular room, covered with square tiles. Each tile is colore

hdu 1251 统计难题 (map水过)

# include <stdio.h> # include <algorithm> # include <string.h> # include <map> # include <iostream> using namespace std; int main() { char a; string x; map<string,int>q; while(true) { scanf("%c",&a); if(a=

[ACM] hdu 1251 统计难题 (字典树)

统计难题 Problem Description Ignatius近期遇到一个难题,老师交给他非常多单词(仅仅有小写字母组成,不会有反复的单词出现),如今老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). Input 输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每一个提问都是一个字符串. 注意:本题仅仅有一组測试数据,处理到文件结束. Out

hdu 1312 Red and Black(BFS水题)

Red and Black Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9684    Accepted Submission(s): 6021 Problem Description There is a rectangular room, covered with square tiles. Each tile is colore

HDU 2566 统计硬币

统计硬币 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7304    Accepted Submission(s): 5016 Problem Description 假设一堆由1分.2分.5分组成的n个硬币总面值为m分,求一共有多少种可能的组合方式(某种面值的硬币可以数量可以为0). Input 输入数据第一行有一个正整数T,表示有

HDU 1251统计难题

D - 统计难题 Time Limit:2000MS     Memory Limit:65535KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 1251 Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). Input 输入数据的第一部分是一张单词表,每行一个单词,单词的长度