ZOJ—— 2165 Red and Black（搜索）

Dear 丶 2021-09-26 11:36 231阅读 0赞

## 题目链接：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2165][http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_2165] ##

## 题目： ##

## [Red and Black][] ##

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> 
    #include<string.h>
    int f[110][110];
    char e[110][110];
    int a,b,c,i,j;
    void q(int x,int y);
    int main()
    {
    	
    	while(scanf("%d%d",&a,&b),a !=0 || b != 0){
    		c = 0;
    		memset(f,0,sizeof(f));
    		gets(e[105]);
    		for(i = 0;i < b;i ++)
    			gets(e[i]);
    		for(i = 0;i < b;i ++){
    			for(j = 0;j < a;j ++){
    				if(e[i][j] == '@'){
    					c = 1;
    					break;
    				}
    			}
    			if(c)
    				break;
    		}
    		c = 0;
    		q(i,j);
    		f[i][j] = 1;
    		printf("%d\n",c);
    	}
    	return 0;
    }
    void q(int x,int y)
    {
    	int i;
    	int next[4][2]={0,1,
    					1,0,
    					0,-1,
    					-1,0};
    	e[x][y] = '-';
    	c ++;
    	for(i = 0;i < 4;i ++){
    		int tx = x + next[i][0];
    		int ty = y + next[i][1];
    		if(tx >= b || tx < 0 || ty >= a || ty < 0 )
    			continue;
    		if(e[tx][ty] == '.' && !f[tx][ty]){
    			f[tx][ty] = 1;
    			q(tx,ty);
    			
    		}
    	}
    	return ;
    }

[http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_2165]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2165
[Red and Black]: https://vjudge.net/problem/ZOJ-2165