dfs/bfs--Red and Black

Red and Black

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

#include<stdio.h>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

typedef pair<int,int> node;//node表示一个点 
bool vis[21][21]; //标记是否访问过 
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; //四个方向
node start ; //起点位置 
int N,M; //N，M分别为行数 列数 
char maze[21][21]; //地图 
int sum; //最后答案 

int bfs(){
	queue<node> q; //新建一个队列q 
	node now,next; //创建两个点，now和next
	now = start; 
	memset(vis,0,sizeof(vis));//初始化 将vis数组全部值设置为false
	vis[now.first][now.second] =true; //将走过的点进行标记
	q.push(now);//将当前值压入队列
	while(q.size()){
		now = q.front(); //将第一个进入队列的元素赋值给now 
		q.pop();//去除第一个进入的元素 
		for(int i=0;i<4;i++){//探索四个方向的坐标 
			next.first = now.first + dx[i];
			next.second = now.second + dy[i];
			if(0<=next.first&&next.first<N&&0<=next.second&&next.second<M&&maze[next.first][next.second]=='.'&&vis[next.first][next.second]==false){
				//不在边界且该点为'.'且该点的还未被访问时，将该点压入q队列中 
				sum++; //总数+1 
				q.push(next); //将该点压入队尾 
				vis[next.first][next.second] = true; //标记该点 为已访问点 
			}
		}
	} 
	return sum; 
} 

int main(){
	
	
	while(1){
		sum =0; 
		scanf("%d%d",&M,&N);
		if(M==0||N==0) break; 
		for(int i=0;i<N;i++){
			scanf("%s",&maze[i]);
			for(int j=0;j<M;j++){
				if(maze[i][j]=='@'){//找到起点位置 
					start.first = i;
					start.second = j;
				}
			}
		}
		int res = bfs()+1;
		printf("%d\n",res);
	}
	return 0;
		
}