Red and Black
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12138 Accepted Submission(s):
7554
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.
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.
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).
which contains the number of tiles he can reach from the initial tile (including
itself).
Sample Input
Sample Output
45
59
6
13
#include <iostream>
#include <cstdio>
using namespace std;
char a[][];
int m,n;
int count=;
void dfs(int x,int y)
{
if(a[x][y]=='.'&&x<n&&x>=&&y<m&&y>=)
{
count++;
a[x][y]='#';
dfs(x+,y);
dfs(x,y+);
dfs(x,y-);
dfs(x-,y);
}
}
int main()
{
freopen("in.txt","r",stdin);
while(scanf("%d%d",&m,&n)&&m!=&&n!=)
{
count=;
int i,j,x,y;
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='@')
{
x=i;y=j;
}
}
}
a[x][y]='.';
dfs(x,y);
cout<<count<<endl;
}
}