I - Red and Black
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64u
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.
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)
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
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13
#include<stdio.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
char a[25][25];
int b[25][25];
int dir[4][2]= {0,1,1,0,0,-1,-1,0};
struct node
{
int x,y;
} w;
int sum=0;
void bfs(int x,int y)
{
queue<node> q;
int k,i,j;
w.x=x;
w.y=y;
q.push(w);
while(!q.empty())
{
node s=q.front();
q.pop();
for(int i=0; i<4; i++)
{
w.x=s.x+dir[i][0];
w.y=s.y+dir[i][1];
if(!b[w.x][w.y]&&a[w.x][w.y]!='#'&&w.x>=1&&w.x<=m&&w.y>=1&&w.y<=n)
{
sum++;
b[w.x][w.y]=1;
q.push(w);
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m)&&(n||m))
{
sum=0;
int i,j,x=0,y=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=1; i<=m; ++i)
scanf("%s",a[i]+1);
for(i=1; i<=m; ++i)
for(j=1; j<=n; ++j)
{
if(a[i][j]=='@')
{
x=i;
y=j;
break;
}
}
b[x][y]=1;
bfs(x,y);
printf("%d\n",sum+1);
}
return 0;
} //#include<iostream>
//#include<string.h>
//#include<stdio.h>
//using namespace std;
//int direct[4][2] = { -1, 0, 1, 0, 0, 1, 0, -1 }; /*定义方向， 左右，上下*/
//char map[21][21]; /*输入的字符串*/
//bool mark[21][21]; /*标记走过的路程*/
//bool flag;
//int W, H;
//int Dx, Dy; //记录起始位置@，从这里开始进行搜索
//int ans; //记录满足的个数。初始化为1，因为@也包含在内
///*****底下是核心算法，主要是从
//上下左右这四个方向进行搜索，注意
//满足搜索的条件是不能越界，不能是#，
//还有就是没有搜索过的--》主要是靠mark[i][j]
//来实现*******/
//void DFS( int x, int y )
//{
// mark[x][y] = true;
// for( int k = 0; k < 4; k ++ )
// {
// int p = x + direct[k][0];
// int q = y + direct[k][1];
// if( p >= 0 && q >= 0 && p < H && q < W && !mark[p][q] && map[p][q] != '#' )
// {
// ans ++;
// DFS( p, q );
// }
// }
// return;
//}
//
//int main()
//{
// int i, j, k;
// while( cin >> W >> H && ( W || H ) ) // W -> column, H -> row;
// {
// memset( mark, false, sizeof( mark ) );
// for( i = 0; i < H; i ++ )
// for( j = 0; j < W; j ++ )
// {
// cin >> map[i][j];
// if( map[i][j] == '@' )
// {
// Dx = i;
// Dy = j;
// }
// }
// ans = 1;
// DFS( Dx, Dy );
// cout << ans << endl;
// }
//}
//
//
// //#include <iostream>
//
//using namespace std;
//char a[50][50];
//int m,n;
//int sum;
//void dfs(int i,int j){
// a[i][j]='#';//把搜素到的点变成#
// sum++;//sum用于计数每搜到一个点就记一下数
// if(i-1>=0&&a[i-1][j]=='.')dfs(i-1,j);
// if(i+1<m&&a[i+1][j]=='.')dfs(i+1,j);
// if(j-1>=0&&a[i][j-1]=='.')dfs(i,j-1);
// if(j+1>=0&&a[i][j+1]=='.')dfs(i,j+1);//四个方向搜素
//}
//int main()
//{
// while(cin>>n>>m&&(m+n)){
// for(int i=0; i<m; i++)
// cin>>a[i];
// sum=0;
// for(int i=0; i<m; i++)
// for(int j=0; j<n; j++){
// if(a[i][j]=='@')
// dfs(i,j);
// }
// cout<<sum<<endl;
// }
// return 0;
//}