A46335. 红与黑有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。输入包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下 1）‘.’：黑色的瓷砖； 2）‘#’：白…
填空题
困难
知识点
题目描述
红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下 1）‘.’：黑色的瓷砖； 2）‘#’：白色的瓷砖； 3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时，表示输入结束。
输出
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0样例输出
45参考答案
#include<iostream>
using namespace std;
int n,m;
int step=0;
char map[30][30]; //用来记录黑白瓷砖
bool visit[30][30]; //用来记录是否走过
int tr[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //定义一个数组来表示每一个位置可以进行的尝试
bool in(int x,int y) //bool型变量判断是否还在规定区域内
{
return 0<=x&&x<n&&0<=y&&y<n;
}
void dfs(int x,int y) //最重要的部分 深搜
{
step++; //用step表示可以走到的砖块数
visit[x][y]=1; //走过的地方记录在 visit中 防止重复
for(int i=0;i<4;i++) //每一个位置都尝试四种可能
{
int tx=x+tr[i][0];
int ty=y+tr[i][1];
if(!visit[tx][ty]&&map[tx][ty]=='.'&&in(tx,ty))
/*判断每一种可能是否符合要求 （1.未走过 2.是可以走的黑（or红）砖 写到这里
原谅博主已经忘记了原题 3.是否还在规定区域内）*/
{
dfs(tx,ty);
}
}
}
int main()
{
cin>>m>>n; //m代表x方向（也就是列) n代表y方向（也就是行）
int x,y;
for(int i=0;i<n;i++) //输入n*m矩阵
for(int j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='@') //判断初始位置 并将其行和列位置赋给x,y记录
{
x=i;
y=j;
}
}
dfs(x,y); //深搜
cout<<step;
return 0;
}
上一题
下一题