#问题求解与编程# 实验三 G小蝌蚪安家

小蝌蚪安家

发布时间: 2018年4月2日 20:48   时间限制: 1000ms   内存限制: 128M

3 3
###
###
##.
2 3
#..
..#

1
4

———————————————————————————————————————————————————非常标准的一道DFS题目 相当有温习的价值和必要

#include<iostream>
#include<string.h>
#include<cmath>
#include <cstdio>
using namespace std;
char map[110][110];
int v[110][110];
int temp,n,m;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main()
{
void dfs(int i,int j);
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
int Max=0;
memset(v,0,sizeof(v));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>map[i][j];//输入地图
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(map[i][j]=='.'&&v[i][j]==0)//对每一块区域都进行DFS搜索
{
temp=0;//area每次重新走的时候都要重置为0
dfs(i,j);
Max=max(Max,temp);
}
//保留其中的最大值
}
}
cout<<Max<<endl;
}
return 0;
}
void dfs(int i,int j)
{
if(i<0||j<0||i>=n||j>=m||v[i][j])
return;//超出范围则return
v[i][j]=1;//标记访问过后的路径
temp++;//
for(int k=0;k<4;k++)
{
int x=i+dir[k][0];
int y=j+dir[k][1];
if(x<0||x>=n||y<0||y>=m)
continue;
if(v[x][y]==0&&map[x][y]=='.')
dfs(x,y);
}
}

DFS问题常封装好DFS函数来解决，关键在于判断DFS搜索的方向和范围。关于方向 通常设置一个dir函数会更加简单一点；直接调用其对应的方向就好。

下面是标程：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,posn;
int vis[110][110];//标记走过的点,0表示没走过,1表示走过
char maps[110][110];//存这个区域
int dir[4][2]={1,0,-1,0,0,1,0,-1};//四个方向
void dfs(int i,int j)
{
if(i<0||i>=n||j<0||j>=m)//筛去不合法的路径
return ;
if(vis[i][j]||maps[i][j]=='#')//如果这个点走过，或者这个点是'#',也不用走了
return ;
posn++;
vis[i][j]=1;//面积pos已经自加1了，所以该点也就可以标记走过了
for(int k=0;k<4;k++)//往四个方向走
dfs(i+dir[k][0],j+dir[k][1]);
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,j,maxn=0;
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
scanf("%s",maps[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(maps[i][j]=='.'&&(!vis[i][j]))//如果是水洼'.'并且这个水洼点'.'没有被计算过，则从这个点开始dfs
{
posn=0;//posn存的是每块水洼的面积，每块计算的时候需要重置为0
dfs(i,j);
maxn=max(maxn,posn);
}
}
printf("%dn",maxn);
}
return 0;
}

最后

以上就是唠叨篮球为你收集整理的#问题求解与编程# 实验三 G小蝌蚪安家的全部内容，希望文章能够帮你解决#问题求解与编程# 实验三 G小蝌蚪安家所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。