ZOJ-2165——Red and Black

柔情只为你懂 2022-03-26 14:29 130阅读 0赞

#                                         [Red and Black][] #

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

###  题意描述： ###

在W\*H的矩形房间里有红色和黑色两种砖块，一个男人站在一块黑色砖块上，男人只能移动上下左右相邻的黑色砖块上，求男人能到达的所有黑色砖块数。

'-'为黑色砖块，'\#'红色砖块，'@'男人所站的黑色砖块。

### 解题思路： ###

直接深搜，模板题。

### 程序代码： ###

#include<stdio.h>
    #include<string.h>
    char map[30][30];
    int num,n,m,book[30][30];
    int xx[4][2]={0,-1,
    			  -1,0,
    			  0,1,
    			  1,0};
    void dfs(int x,int y)
    {
    	int k,i,j,tx,ty;
    	for(k=0;k<4;k++)
    	{
    		tx=x+xx[k][0];
    		ty=y+xx[k][1];
    		if(tx>=0&&tx<n&&ty>=0&&ty<m&&book[tx][ty]==0)
    		{
    			book[tx][ty]=1;
    			num++;
    			dfs(tx,ty);
    		}
    	}
    	return;
    }
    int main()
    {
    	int i,j,x,y;
    	while(scanf("%d%d",&m,&n))
    	{
    		if(n==0&&m==0)
    			break;
    		num=0;
    		for(i=0;i<n;i++)
    			scanf("%s",map[i]);
    		for(i=0;i<n;i++)
    			for(j=0;j<m;j++)
    			{
    				if(map[i][j]=='#')
    					book[i][j]=1;
    				else
    					book[i][j]=0;
    				if(map[i][j]=='@')
    				{
    					x=i;
    					y=j;
    				}
    			}
    		num++;
    		book[x][y]=1;
    		dfs(x,y);
    		printf("%d\n",num);
    	}
    	return 0;
     }

[Red and Black]: https://vjudge.net/problem/ZOJ-2165