首页 > 代码库 > DFS 深度优先搜索例题
DFS 深度优先搜索例题
约翰的农场被暴风雨给淹没了，损失很大，他的保险公司将支付给他，但是支付金额取决于被淹没的最大面积。这个农场是一个边长分别为n、m的矩形，包含nm个空间，每个空间要么是干的，要么是被淹没的，一共有k个空间被淹没。求最大的淹没面积。
题目分析：首先建立坐标，标记被淹没的空间，然后从左上角搜索被淹没的空间，并取消标记，再以此为中心向四周搜索是否有被淹没的空间，有的话继续计数并取消标记，以此类推，找出所有被淹没的空间，最后排序，找到被淹没最大的面积。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[110][110];
int num[110];
int ans,n,m;
void dfs(int x,int y) //深度优先搜索
{
if(a[x][y]==1||x<1||x>n||y<1||y>m) //判断是否越界，是否是被淹没的
return ;
num[ans]++; //计数
a[x][y]=1;
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main()
{
int i,j,k,x,y;
while(~scanf("%d%d%d",&n,&m,&k))
{
ans=-1;
memset(num,0,sizeof(num)); //初始化
for(i=1;i<=n;i++) //建立坐标
for(j=1;j<=m;j++)
a[i][j]=1;
while(k--)
{
scanf("%d%d",&x,&y); //标记被淹没的
a[x][y]=0;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(a[i][j]==0) //搜索被淹没的
{
ans++;
dfs(i,j);
}
}
sort(num,num+ans+1); //快排
printf("%d\n",num[ans]);
}
return 0;
}
题目大意：春天来了，汤姆有一块包含n*m个方块良田，他有一个耕种机器（位于左上角），但是其中有一些方块田地有大石块，机器不能通过，然而他想把没有石块的全部良田耕种，可能吗？
题目分析：首先利用字符串建立地图，找出所以有石块的田地并计数，然后从左上角搜索没有石块的良田并标记计数，然后判断下一块田地是否可以耕种，以此类推，直到不能再耕种，判断所记的数目是否等于所有田地的总数目
- #include <stdio.h>
- #include <string.h>
- char str[10][10];
- int n,m,sum;
- bool flag;
- void dfs(int x,int y) //深度优先搜索
- {
- if(x<0||x>n-1||y<0||y>m-1||str[x][y]==‘S‘) //排除不符合条件的
- return ;
- sum++;
- str[x][y]=‘S‘; //标记
- if(sum==n*m) //判断是否可以全部耕种
- {
flag=true;
- return ;
- }
- dfs(x-1,y);
- dfs(x+1,y);
- dfs(x,y-1);
- dfs(x,y+1);
- sum--;
- str[x][y]=‘.‘;
- }
- int main()
- {
- int i,j;
- while(scanf("%d%d",&n,&m),n||m)
- {
- sum=0;
- flag=false;
- for(i=0;i<n;i++) //利用字符串输入，省时
- scanf("%s",&str[i]);
- for(i=0;i<n;i++) //找出有石块的田地
- for(j=0;j<m;j++)
- if(str[i][j]==‘S‘)
- sum++;
- dfs(0,0);
- if(flag)
- puts("YES");
- else
- puts("NO");
- }
- return 0;
}
从 k数组中选择 6 个元素的组合，写出所有的可能情况。
题目分析：其实这个题目有个不好处理的就是最后一个案例不能有换行。把案例看成以文件读入读出，第一个输出不换行，第二个输入再换行。递归实现从 n 个元素中选择 m 个元素，常规法.从头到尾一个一个的找（深度优先搜寻），并递归替换。
#include <stdio.h>
- #include <string.h>
- int a[50],b[7];
- int n;
- void dfs(int top,int sum) //深度优先搜索
- {
- if(sum>=6) //满足条件输出
- {
- for(int i=0;i<6;i++)
- {
- if(i)
- printf(" ");
- printf("%d",b[i]);
- }
- puts("");
- return ;
- }
- for(int i=top;i<n;i++) //不满足条件继续搜索
- {
- b[sum]=a[i];
- dfs(i+1,sum+1);
- }
- return ;
- }
- int main()
- {
- int j;
- while(scanf("%d",&n),n)
- {
- if(j++) //输出空行
- puts("");
- for(int i=0;i<n;i++)
- scanf("%d",&a[i]);
- dfs(0,0);
- }
- return 0;
- }
变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体。现在将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse)。
题目分析：首先搜索首字母为“B”的单词，然后标记已搜索过，再搜索首字母为上一个单词的尾字母并标记，直到找到尾字母为“M”的单词，输出“Yes.”，如果搜索不到此单词输出“No.”。
#include <stdio.h>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- int vis[1000];
- int flag,k;
- struct node //构建结构体，分别记录单词的首字母和尾字母
- {
- int start;
- int end;
- }word[1000];
- void dfs(char c) //深度优先搜索
- {
- char temp;
- if(c==‘m‘) //判断是否找到字母“M”
- {
- flag=1;
- return ;
- }
- for(int i=1;i<k;i++)
- if(vis[i]==0&&word[i].start==c) //单词没有被搜索过，并且首字母为上一个字母的尾字母
- {
- temp=c;
- c=word[i].end;
- vis[i]=1; //对于搜索过的单词进行标记
- dfs(c);
- c=temp;
- }
- }
- int main()
- {
- int i,len;
- char a[100];
- k=1; //初始化
- while(gets(a)!=NULL)
- {
- if(strcmp(a,"0")==0) //判断是否输入结束
- {
- flag=0;
- dfs(‘b‘); //搜索首字母为“b” 的单词
- if(flag)
- puts("Yes.");
- else
- puts("No.");
- k=1; //初始化
- }
- else
- {
- len=strlen(a);
- word[k].start=a[0];
- word[k].end=a[len-1];
- vis[k]=0;
- k++;
- }
- }
- return 0;
- }
在有若干个城墙的n*n的城市里建立大炮，大炮威力很大，除了城墙都能打透，所以两门大炮不能在同一行，或同一列，除非中间有城墙隔着，问最多能建立多少个大炮。
题目分析：从左上角开始搜索，判断是否能安排大炮（此位置的上方和左方不能有大炮，除非有城墙隔着），能安排大炮就标记并统计大炮数目，以此类推，直到所有地方不能安排大炮，输出最多安排大炮的数量。
#include <stdio.h>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- char str[5][5];
- int t,sum;
- bool vis(int x,int y) //判断此位置的上方，左方是否有大炮或者城墙
- {
- int i;
- for(i=x-1;i>=0;i--)
- {
- if(str[i][y]==‘0‘)
- return false;
- if(str[i][y]==‘X‘)
- break;
- }
- for(i=y-1;i>=0;i--)
- {
- if(str[x][i]==‘0‘)
- return false;
- if(str[x][i]==‘X‘)
- break;
- }
- return true;
- }
- void dfs(int x,int y)
- {
- int a,b;
- if(x==t*t) //是否已经全部搜索完毕
- {
- if(y>sum) //sum为最多大炮数量
- {
- sum=y;
- return ;
- }
- }
- else
- {
- a=x/t; //a为行数
- b=x%t; //b为列数
- if(str[a][b]==‘.‘&&vis(a,b)) //判断此位置是否为空地
- {
- str[a][b]=‘0‘; //标记已安排大炮
- dfs(x+1,y+1); //搜索数目和安排的大炮数目分别+1
- str[a][b]=‘.‘;
- }
- dfs(x+1,y); //搜索数目+1
- }
- }
- int main()
- {
- int i;
- while(scanf("%d",&t)&&t)
- {
- sum=0;
- for(i=0;i<t;i++) //输入地图
- scanf("%s",str[i]);
- dfs(0,0); //从左上角开始搜索
- printf("%d\n",sum);
- }
- return 0;
- }
用自己已有的卡片等价交换自己想要的卡片，一共有多少种交换方法。
题目分析：首先将自己所拥有的卡片的价值和数量输入并保存在结构体中，然后进行卡片交换，记录一共有多少种符合等价交换的交换方式
#include <stdio.h>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- int sum,m;
- struct note //建立结构体
- {
- int value;
- int num;
- }a[11];
- void dfs(int x,int y,int z) //深度优先搜索
- {
- if(y==z) //符合条件
- {
- sum++;
- return ;
- }
- if(y>z||x==m) //价值超出，不符合条件
- return ;
- for(int j=0;j<=a[x].num;j++)
- dfs(x+1,y+j*a[x].value,z); //递归
- }
- int main()
- {
- int n,i,b=-1;
- while(~scanf("%d%d",&n,&m))
- {
- for(i=0;i<m;i++)
- scanf("%d%d",&a[i].value,&a[i].num);
- b++;
- if(b)
- puts("");
- sum=0;
- dfs(0,0,n);
- printf("%d\n",sum);
- }
- return 0;
- }
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，...，wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。如果有满足条件的选择，则此背包有解，否则此背包问题无解。第一行为物品重量S（整数）； 第二行为物品数量n， 第三行为n件物品的重量的序列。
有解就输出”yes!“，没有解就输出”no!“。
#include <iostream>
#include <cstring>
using namespace std;
int wsum = 0;//背包里总重量
int flag = 0;//旗帜法
int book[100];//标记法
void DFS(int S, int m, int w[])//深搜算法
{
if (wsum == S)
{
flag = 1;
return;
}
else
{
for (int i = 0; i < m; i++)
{
if (book[i] == 0)
{
wsum += w[i];
book[i] = 1;
DFS(S, m, w);
wsum -= w[i];
book[i] = 0;
}
}
}
return;
}
int main()
{
memset(book, 0, sizeof(book));
int w[100];
int S, m;
cin >> S >> m;
for (int i = 0; i < m; i++)
cin >> w[i];
DFS(S, m, w);
if (flag == 1)
cout << "yes!";
else
cout << "no!";
return 0;
}
DFS 深度优先搜索例题