Red and Black（DFS 深搜练习）
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.
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)
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).
题意：就是N*m的迷宫里面，@ 代表入口，然后 . 代表能通行，#代表不能通行，然后问你从@开始能走多少个格子，也就是连通性问题！
思路：可以理解为像树一样从根部开始，然后的话就往下是各个根，每条路都到达根的底部。
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
char s[25][25];
int flag;
void dfs(int a, int b)
{
if (s[a + 1][b] == '.')
{
s[a + 1][b] = '#';
flag++;
dfs(a + 1, b);
}
if (s[a - 1][b] == '.')
{
s[a - 1][b] = '#';
flag++;
dfs(a - 1, b);
}
if (s[a ][b+1] == '.')
{
s[a][b + 1] = '#';
flag++;
dfs(a,b+1);
}
if (s[ a ][b-1] == '.')
{
s[a][b-1] = '#';
flag++;
dfs(a ,b-1);
}
}
int main()
{
int i, j, k, n, m;
char c;
while (cin >> n >> m&&(n+m)){
flag = 0;
int a, b;
for (i = 0; i <25; i++)
for (j = 0; j < 25; j++)
s[i][j] = '#';
for (i = 0; i < m; i++){
for (j = 0; j < n; j++){
cin >> s[i][j];
if (s[i][j] == '@')
{
a = i;
b = j;
}
}
}
dfs(a, b);
cout << flag+1 << endl;
}
return 0;
}然后按照正常的板子来写的话 应该是如下
/*
搜索入门题
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char map[25][25];
bool vis[25][25];
int s,e;
int N,M;
int mov[4][2]={0,1,1,0,0,-1,-1,0};
bool Judge(int x,int y){
if(x>=0&&x<N&&y>=0&&y<M)return true;
return false;
}
int step;
void DFS(int x,int y){
int xx=x;
int yy=y;
for(int i=0;i<4;i++){
x=xx+mov[i][0];
y=yy+mov[i][1];
if(Judge(x,y)&&map[x][y]=='.'&&vis[x][y]==0)
{
step++;
vis[x][y]=1;
DFS(x,y);
}
}
return;
}
int main(){
while(scanf("%d%d",&M,&N)!=EOF){
if(M==0&&N==0)break;
memset(vis,0,sizeof(vis));
memset(map,0,sizeof(map));
for(int i=0;i<N;i++){
scanf("%s",map[i]);
}
int x,y;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(map[i][j]=='@'){
x=i;
y=j;
}
}
}
//printf("%d %d\n",x,y);
step=1;
vis[x][y]=1;
DFS(x,y);
printf("%d\n",step);
}
return 0;
}腾讯云开发者
