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;
}
相关文章
|
6月前
|
Java
hdu-1312-Red and Black
hdu-1312-Red and Black
33 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
84 0
|
机器学习/深度学习 Windows
Codeforces Round #748 (Div. 3) F - Red-Black Number (记忆化搜索)
Codeforces Round #748 (Div. 3) F - Red-Black Number (记忆化搜索)
101 0
AtCoder Beginner Contest 222 E - Red and Blue Tree(dfs dp)
AtCoder Beginner Contest 222 E - Red and Blue Tree(dfs dp)
115 0
hdu 1312 Red and Black(BFS)
hdu 1312 Red and Black(BFS)
144 0
hdu 1312 Red and Black
一个人从@点出发,求他所能到达的'.'的数目,'#'不可走,@本身算1个点。 思路:搜索入门题。
150 0
HDOJ 1312 (POJ 1979) Red and Black
HDOJ 1312 (POJ 1979) Red and Black
113 0
Codeforces 833D Red-black Cobweb【树分治】
D. Red-black Cobweb time limit per test:6 seconds memory limit per test:256 megabytes input:standard input output:standard o...
1436 0
|
Java 机器学习/深度学习
HDU 1556 Color the ball
Color the ball Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 18404    Accepted Submission(s...
830 0