深度优先练习【1216：红与黑】

向右看齐 2022-12-21 06:12 83阅读 0赞

# 1216：红与黑 #

> 时间限制: 1000 ms 内存限制: 65536 KB  
> 测试地点：[http://ybt.ssoier.cn:8088/problem\_show.php?pid=1216][http_ybt.ssoier.cn_8088_problem_show.php_pid_1216]

## 【题目描述】 ##

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

## 【输入】 ##

包括多组数据。每组数据的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:

1）‘.’：黑色的瓷砖；

2）‘\#’：白色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每组数据中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

## 【输出】 ##

对每组数据，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

## 【输入样例】 ##

6 9 
    ....#.
    .....#
    ......
    ......
    ......
    ......
    ......
    #@...#
    .#..#.
    0 0

## 【输出样例】 ##

这很明显是一道深度优先搜索的题目：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    char mapp[500][500];
    int pre,pry,m,n;
    int dfs(int x,int y){ 
    	if(x < 0 || x >= n || y >= m || y < 0){ 
    		return 0;
    	}
    	if(mapp[x][y] == '#'){ 
    		return 0;
    	}
    	if(mapp[x][y] != '#'){ 
    		mapp[x][y] = '#';
    		return  1 + dfs(x + 1,y) + dfs(x - 1,y) + dfs(x,y + 1) + dfs(x,y - 1);
    	}	
    }
    int main(){ 
    	int startx,starty;
    	while(true){ 
    		cin >> m >> n;
    		if(m != 0 && n != 0){ 
    			for(int i = 0;i < n;i++){ 
    				for(int j = 0;j < m;j++){ 
    					cin >> mapp[i][j];
    					if(mapp[i][j] == '@'){ 
    						startx = i;
    						starty = j; 
    					} 
    				}
    			}
    			int ans = dfs(startx,starty);
    			cout << ans << endl;
    		}else{ 
    			break;
    		}
    	}
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]

[http_ybt.ssoier.cn_8088_problem_show.php_pid_1216]: http://ybt.ssoier.cn:8088/problem_show.php?pid=1216
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/65b5d3b9074a4b748f48fc2efbb1cf8e.png