HDU-1312,Red and Black(DFS)

简介: HDU-1312,Red and Black(DFS)

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


.#.........


.#.#######.


.#.#.....#.


.#.#.###.#.


.#.#..@#.#.


.#.#####.#.


.#.......#.


.#########.


...........


11 6


..#..#..#..


..#..#..#..


..#..#..###


..#..#..#@.


..#..#..#..


..#..#..#..


7 7


..#.#..


..#.#..


###.###


...@...


###.###


..#.#..


..#.#..


0 0


Sample Output:


45


59


6


13


程序代码:  


#include<stdio.h>
int w,h;
char s[25][25];
int dfs(int x,int y)
{
    if(x<0||x>=w||y<0||y>=h)
        return 0;
    if(s[x][y]=='#')
        return 0;
    else
    {
        s[x][y]='#';
        return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1);
    }
}
int main()
{
    int i,j;
    while(scanf("%d %d",&h,&w)&&w!=0&&h!=0)
    {
        for(i=0;i<w;i++)
            scanf("%s",s[i]);
        for(i=0;i<w;i++)
        {
            for(j=0;j<h;j++)
            {
                if(s[i][j]=='@')
                    printf("%d\n",dfs(i,j));
            }
        }
    }
    return 0;
}
相关文章
|
8月前
|
Java
hdu-1312-Red and Black
hdu-1312-Red and Black
38 0
HDU - 1312 Red and Black(DFS)
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
92 0
AtCoder Beginner Contest 222 E - Red and Blue Tree(dfs dp)
AtCoder Beginner Contest 222 E - Red and Blue Tree(dfs dp)
127 0
CodeForces - 1469B Red and Blue (前缀和)
CodeForces - 1469B Red and Blue (前缀和)
106 0
hdu 1312 Red and Black(BFS)
hdu 1312 Red and Black(BFS)
149 0
hdu 1312 Red and Black
一个人从@点出发,求他所能到达的'.'的数目,'#'不可走,@本身算1个点。 思路:搜索入门题。
158 0
HDOJ 1312 (POJ 1979) Red and Black
HDOJ 1312 (POJ 1979) Red and Black
118 0
|
Java
HDOJ 1312题Red and Black
HDOJ 1312题Red and Black
129 0
【1069】The Black Hole of Numbers (20 分)
【1069】The Black Hole of Numbers (20 分) 【1069】The Black Hole of Numbers (20 分)
109 0