poj–1979 Red and Black

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)
The end of the input is indicated by a line consisting of two zeros.

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

A person in the room @ place, the room is covered with red and black tiles, this person only allowed to walk in black tiles, not red tiles
　　　　　The black tiles are represented by "."
　
Problem Solution: This problem is to search the problem can be used DFS and BFS two ways, this problem is better to use DFS, find the person's starting position, starting from this starting position search
　　　Until the search is finished.

Code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int W,H;
char map[21][21];
int dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
int ans;
void DFS(int x,int y)
{
    map[x][y]='#';//It shows that we have passed the tile.Ans++;　　//I want to increase myself.int tx,ty;
    for(int i=0;i<4;i++)
    {
        tx=x+dir[i][1];
        ty=y+dir[i][0];
        if(tx>=0 && ty>=0 && tx<H && ty<W && map[tx][ty]=='.')
        {
            DFS(tx,ty);
        }
    }
}
int main()
{
    while(scanf("%d%d",&W,&H)!=EOF)
    {
        if(W==0&&H==0)    break;
        ans=0;
        int x,y;
        for(int i=0;i<H;i++)
        {
            for(int j=0;j<W;j++)
            cin>>map[i][j];
        }
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++)
            {
                if(map[i][j]=='@')
                {
                    x=i;
                    y=j;
                }
            }
        DFS(x,y);
        printf("%d\n",ans);
    }
    return 0;
}

Leave a Reply Cancel reply