poj 1979 Red and Black（dfs水题）

2022-03-06 15:00:29

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 . 

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

....#.

.....#

......

......

......

......

......

#@...#

.#..#.

.#.........

.#.#######.

.#.#.....#.

.#.#.###.#.

.#.#..@#.#.

.#.#####.#.

.#.......#.

.#########.

...........

..#..#..#..

..#..#..#..

..#..#..###

..#..#..#@.

..#..#..#..

..#..#..#..

..#.#..

..#.#..

###.###

...@...

###.###

..#.#..

..#.#..

Sample Output

Source

Japan 2004 Domestic

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define N 26

 int n,m;

 char mp[N][N];

 int x,y;

 int vis[N][N];

 int ans;

 int dirx[]={,,-,};

 int diry[]={-,,,};

 void dfs(int sx,int sy){

     for(int i=;i<;i++){

         int xx=sx+dirx[i];

         int yy=sy+diry[i];

         if(vis[xx][yy]) continue;

         if(mp[xx][yy]=='#') continue;

         if(xx< || xx>=n || yy< || yy>=m) continue;

         vis[xx][yy]=;

         ans++;

         dfs(xx,yy);

     }

 }

 int main()

 {

     while(scanf("%d%d",&m,&n)== && n+m){

         for(int i=;i<n;i++){

             scanf("%s",mp[i]);

             for(int j=;j<m;j++){

                 if(mp[i][j]=='@'){

                     x=i;y=j;

                 }

             }

         }

         memset(vis,,sizeof(vis));

         ans=;

         vis[x][y]=;

         dfs(x,y);

         printf("%d\n",ans);

     }

     return ;

 }

码农公寓

相关文章