前言
写这篇博客前，我有些题做不出来，就在CSDN上看别人写的题解，大佬们的AC代码动辄一百多行，各种骚操作，但是我就是看不懂，只觉得大佬们好厉害啊好强啊，但是对我们这些刚学DFS的萌新初学者并没什么用，反而还可能被劝退(蒟蒻只能蹲在墙角看着大佬们的代码瑟瑟发抖)。然而我自己写完后，删去不必要的冗余代码，发现AC代码也不过四五十行，原来DFS也不是想象中的那么难嘛。很多题竟然三十行代码就能解决，我之前还差点被那些题给劝退…所以我就写了这篇博客，尽量把代码写得简短和通俗易懂，加上了一些注释，希望能帮助到刚学DFS的萌新（好吧其实我也是刚学的小萌新啊）
题目分析
进入正题。DFS，英文全称Depth First Search，也就是深度优先搜索。
听名字感觉挺高大上，但是其实只是递归的熟练运用，并没有想象的那么难！
本次训练共11题，A题~H题是搜图走迷宫的题，有固定的套路和模式，用来当做DFS入门训练是很好的选择；I题和J题是根据题目的具体背景写递归函数，没有固定套路，有些难度；最后的K题要求最少次数，用BFS(广度优先搜索)比较方便，当然用DFS剪枝后也能做，只是比较麻烦。最好的学习就是从题目中领会DFS的方法（套路）了！
A题 nefu 558 迷宫寻路-搜索
数据保证迷宫边界为障碍物且只有两个不同的入口，那么先在迷宫边界找到起点(beginx , beginy)和终点(endx , endy)，然后从起点开始深度优先搜索，在每次搜索过程中把搜索过的点变成“墙”，防止下次重复搜索。如果能搜索到终点，那么终点就会变成“墙”，这时输出YES即可，否则输出NO。
#include <bits/stdc++.h>
using namespace std;
string a[1001];
int n,m,beginx,beginy,endx,endy,newx,newy;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//定义上下左右四个方向
void seek_begin()//搜索起点
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]=='*'&&(i==0||i==n-1||j==0||j==m-1)){beginx=i;beginy=j;return;}
}
void seek_end()//搜索终点
{
for(int i=n-1;i>=0;i--)
for(int j=m-1;j>=0;j--)
if(a[i][j]=='*'&&(i==0||i==n-1||j==0||j==m-1)){endx=i;endy=j;return;}
}
void dfs(int x,int y)
{
a[x][y]='#';//把搜索过的点变成“墙”，防止下次重复搜索
for(int i=0;i<4;i++)//四个方向搜索新节点
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&a[newx][newy]=='*')//新节点在边界内且未被搜索
dfs(newx,newy);//继续搜索新节点
}
}
int main()
{
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
cin>>a[i];//把string当二维数组用的时候一定要从a[0]开始输入！
seek_begin();seek_end();
dfs(beginx,beginy);
if(a[endx][endy]=='#')printf("YES\n");
else printf("NO\n");
}
return 0;
}
B题 nefu 784 白与黑-搜索
DFS基础题，找到“@”后开始搜索并记录步数即可。
#include <bits/stdc++.h>
using namespace std;
int n,m,sum,newx,newy;
string a[101];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int dfs(int x,int y)
{
a[x][y]='#';
for(int i=0;i<4;i++)
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=0&&newx<m&&newy>=0&&newy<n&&a[newx][newy]!='#')
sum++,dfs(newx,newy);
}
}
int main()
{
while(cin>>n>>m&&n&&m)
{
for(int i=0;i<m;i++)
cin>>a[i];
sum=1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(a[i][j]=='@')dfs(i,j);
printf("%d\n",sum);
}
return 0;
}
C题 nefu 912 搜索入门-搜索
A题的简单版本，不多说。
#include <bits/stdc++.h>
using namespace std;
string a[5];
int n,newx,newy;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
a[x][y]='*';
for(int i=0;i<4;i++)
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=1&&newx<=4&&newy>=1&&newy<=4&&a[newx][newy]=='#')
dfs(newx,newy);
}
}
int main()
{
cin>>n;
while(n--)
{
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
cin>>a[i][j];
dfs(1,1);
if(a[4][4]=='*')printf("YES\n");
else printf("NO\n");
}
return 0;
}
D题 nefu 1693 瓷砖-搜索
这题和B题重复了，题目和代码都是一样的，我就不写了。
E题 nefu 1694 最大黑***域-搜索
这题要你求几块联通区域中最大的联通区域的面积。
先用cnt记录第cnt个黑色联通区域，然后用ans[cnt]记录第cnt个黑色联通区域的面积，求出最大的ans[cnt]即可。
（PS.老师悄咪咪地改了数据，n应该是小于等于1000，不是小于等于100，数组如果只开到100会Runtime Error）
#include <bits/stdc++.h>
using namespace std;
int n,m,mx,cnt,newx,newy,ans[1001],a[1001][1001];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
a[x][y]=0;
ans[cnt]++;
mx=max(ans[cnt],mx);
for(int i=0;i<4;i++)//这里的i一定不能定义为全局变量，否则会错！
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&a[newx][newy]==1)
dfs(newx,newy);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
mx=cnt=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]==1){dfs(i,j);cnt++;}
printf("%d\n",mx);
return 0;
}
F题 nefu 1696 猴群-搜索
E题的简单版本，只要你求联通区域有几块。不多说。
#include <bits/stdc++.h>
using namespace std;
int n,m,sum,newx,newy;
string a[101];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
a[x][y]='0';
for(int i=0;i<4;i++)
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&a[newx][newy]!='0')
dfs(newx,newy);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
sum=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]!='0'){dfs(i,j);sum++;}
printf("%d\n",sum);
return 0;
}
G题 nefu 1699 面积(area)-搜索
这题有点意思，有点像围棋。有一块联通的0区域被1所包围且1是闭合曲线，要求这块0区域的大小，相当于1组成的闭合曲线把所有的0分割成了两部分，一部分的0在包围圈里面，另一部分的0在包围圈外面，那么我们可以搜索包围圈外的0，把外面的所有0都变成1，之后再统计矩阵中还剩下多少个0，也就得到了包围圈内0的数量。包围圈最大的情况是1全部在矩阵的边界上构成一个边长为10的正方形，这时在边界上搜不到0，包围圈内0的个数就是矩阵中所有0的个数；其他的所有情况，包围圈都会比矩阵边界(i=1,i=10,j=1,j=10)小，也就是说，在边界上找到任何一个0就可以开始搜索，每搜索到1个点，若为0，就把它变成1，这样就能使包围圈外所有的0变成1。
#include <bits/stdc++.h>
using namespace std;
int sum,newx,newy,beginx,beginy,a[110][110];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
a[x][y]=1;
for(int i=0;i<4;i++)
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=1&&newx<=10&&newy>=1&&newy<=10&&a[newx][newy]==0)
dfs(newx,newy);
}
}
int main()
{
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
cin>>a[i][j];
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
if(a[i][j]==0&&(i==1||i==10||j==1||j==10))dfs(i,j);//在矩阵边界上开始搜索，把包围圈外的0都变成1
sum=0;
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
if(a[i][j]==0)sum++;
printf("%d\n",sum);
return 0;
}
H题 nefu 1702 01迷宫-搜索（原题：洛谷P1141）
输入m次起点，每次都要重置vis访问标记，然后再进行m次DFS，这样写其实时间复杂度比较高，但是在林大OJ能过（林大OJ的数据很水）。以下代码在林大OJ提交，40ms就能AC，但是提交到洛谷的原题P1141 就会TLE三个点！
//原算法，林大AC，洛谷TLE
#include <iostream>//定义了y0就不能用万能头文件，因为在C++的math.h库中已经有了y0这个变量
#include <cstring>//memset函数的头文件
using namespace std;
char a[1001][1001];
int n,m,x0,y0,sum,newx,newy,vis[1001][1001];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
vis[x][y]=1;
for(int i=0;i<4;i++)
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=1&&newx<=n&&newy>=1&&newy<=n&&vis[newx][newy]==0&&a[newx][newy]!=a[x][y])
sum++,dfs(newx,newy);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
while(m--)
{
sum=1;
cin>>x0>>y0;
memset(vis,0,sizeof(vis));//每次输入起点后都要重置vis访问标记数组
dfs(x0,y0);
cout<<sum<<endl;
}
return 0;
}
我们继续改进算法，降低时间复杂度。
不难发现，在同一个联通块内的所有a[i][j]答案是一样的。
所以我们可以每遇到一个未访问的节点就开始DFS(vis访问标记数组不重置)，这样就能搜索出不同的联通块。为了区分不同的联通块，用cnt记录联通块的序号。再开一个flag二维数组表示a[i][j]属于第cnt个联通块，每次搜索时 ans[flag[x][y]]+1 进行答案的更新。
这样改进算法后我们就不需要每次都从起点开始DFS，而是在输入起点坐标之前就把每个联通块的面积储存起来，之后再输入起点坐标时，就能直接找到这个起点属于的是第cnt个联通块，输出这个联通块的面积即可。
以下代码在洛谷原题P1141中成功AC，耗时477ms。
把cin输入( cin前面有ios::sync_with_stdio(false) )全部改成scanf输入后，耗时326ms。
//改进算法，洛谷成功AC
#include <iostream>
using namespace std;
char a[1001][1001];
int n,m,x0,y0,cnt,newx,newy,vis[1001][1001],flag[1001][1001],ans[1000001];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
vis[x][y]=1;
flag[x][y]=cnt;//a[x][y]属于第cnt个联通块
ans[flag[x][y]]++;//第cnt个联通块的面积+1
for(int i=0;i<4;i++)
{
newx=x+dir[i][0];
newy=y+dir[i][1];
if(newx>=1&&newx<=n&&newy>=1&&newy<=n&&a[newx][newy]!=a[x][y]&&vis[newx][newy]==0)
dfs(newx,newy);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(vis[i][j]==0){cnt++;dfs(i,j);}//更新联通块的序号并且搜索出第cnt个联通块
while(m--)
{
cin>>x0>>y0;
cout<<ans[flag[x0][y0]]<<endl;
}
return 0;
}
I题 数的划分-搜索
数的划分-搜索
Problem:I
Time Limit:2000ms
Memory Limit:65535K
Description
将整数 n 分成 k 份，且每份不能为空，问有多少种不同的分法。当 n=7, k=3 时，下面三种分法被认为是相同的：1,1,5; 1,5,1; 5,1,1
Input
一行两个数 n, k
Output
一行一个整数，即不同的分法数。
Sample Input
7 3
Sample Output
4
这题其实是递归的应用，和DFS关系不大。第一个数从1开始，不断递增，寻找之后的数。每次找的数设为now传入函数中，cnt表示已经找了cnt个数，sum记录已经找的数之和。为了不出现重复搜索(比如511,151,115)，可以假设前面的数大于等于后面的数，假设现在搜索到的i是第cnt个数，后面还有k-cnt个数，后面的数的和最大不超过i*(k-cnt)，再加上原来的sum后，不能大于n，所以有sum+i*(k-cnt)<=n，这也就是剪枝优化了。
#include <bits/stdc++.h>
using namespace std;
int n,k,ans=0;
void dfs(int now,int sum,int cnt)
{
if(cnt==k)//已经找了k个数了，可以返回上一层了，在return之前判断是否满足sum==n，满足就ans+1
{
if(sum==n)ans++;
return;//不能写成else return;
}
for(int i=now;sum+i*(k-cnt)<=n;i++)//sum+i*(k-cnt)<=n 剪枝优化，排除不可能的情况
dfs(i,sum+i,cnt+1);
}
int main()
{
cin>>n>>k;
dfs(1,0,0);
printf("%d\n",ans);
return 0;
}
J题 nefu 1672 艾拉的选举
这题应该是11道题中最难的一个了，难点在于如何写出一个递归函数，让所有评委对所有学生打分使学生得到不同的排名。我们可以先从第1个评委对第1个学生的评分开始搜索，写一个dfs函数，传入k表示评委序号，传入x表示学生序号，如果第k个评委没有评分完所有的学生或者所有的评委没有评分完所有的学生，那么就用一个vis访问标记数组判断第k个评委评分时是否已经用了b[i]这个分数，如果b[i]这个分数还被没用到，就对第x个学生用这个评分，并继续搜索第k个评委对第x+1个学生的评分，注意对第x+1个学生的评分搜索完成后要把vis访问标记数组和第x个学生的分数复原，防止搜索下一个打分方案时出现和上一次一样的打分方案(我们要的是不同的打分方案)，最后当所有的评委都已经完成评分时，按规则排序，更新答案，再返回上一层，不断返回上一层直到又回到第1个评委对第1个学生的打分状态，这时这个评委只能选择和上一次不同的b[i]开始评分了，无法选择和上一次一样的打分方案。这样每次都从第1个评委对第1个学生的打分开始，递归下去到最后一个评委对最后一个学生打完分，更新答案，接着又不断返回上一层到第1个评委对第1个学生的打分的初始状态…直到最后某一次第一个评委对第一个学生的打分时，所有的vis访问标记数组都变成了1，此时无法再打分了，不会再进入到dfs(k,x+1)的下一层递归中，终于把所有的打分方案都遍历了一遍，结束了！(想清楚这个递归的过程并且把代码写出来还真不容易啊…）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,b[5],vis[5][5],ans[5][5];//vis判断第k个评委评分时是否已经用了b[i]这个分数，ans记录答案
struct node
{
ll num,mark;//定义学生的序号和成绩
}a[5];
bool cmp(node a,node b)//按规则排序
{
if(a.mark!=b.mark)return a.mark>b.mark;
return a.num<b.num;
}
void dfs(ll k,ll x)//搜索第k个评委对第x个学生的评分
{
if(x==n+1){dfs(k+1,1);return;}//第k个评委对所有的学生都已经完成评分，搜索下一个评委的评分，搜索完毕后返回上一层
if(k==m+1)//所有的评委都已经完成评分
{
node t[5];//定义临时数组，防止排序后原数组改变
for(int i=1;i<=n;i++) t[i]=a[i];
sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;i++) ans[t[i].num][i]++;//按规则排序后，记录第i个学生得到第j名的打分方案的数量
return;//排序完成后返回上一层
}
for(int i=1;i<=n;i++)
{
if(vis[k][i]==0)//如果第k个评委评分时还没有用b[i]这个分数
{
vis[k][i]=1;
a[x].mark=a[x].mark+b[i];
dfs(k,x+1);//第k个评委继续评分下一个学生，搜索完成后重置vis访问标记，并复原第x个学生的得分
vis[k][i]=0;
a[x].mark=a[x].mark-b[i];
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{cin>>a[i].mark;a[i].num=i;}
for(int i=1;i<=n;i++)
cin>>b[i];
dfs(1,1);//从第1个评委对第1个学生的打分开始搜索
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
j==n?printf("%lld\n",ans[i][j]):printf("%lld ",ans[i][j]);
return 0;
}
K题 nefu 1697 奇怪的电梯-搜索
求最少次数，用BFS(广度优先搜索)比较方便。当然用DFS剪枝后也能做，但是有点麻烦。
我比较追求代码的简洁高效，所以这里只给出BFS的代码，本题用BFS应该比用DFS要好一点。
#include <bits/stdc++.h>
using namespace std;
int n,i,a,b,ans,newx,k[201],vis[201];//a为起点，b为终点，k[i]记录到第i层时可以向上或向下移动的层数，vis标记是否已被访问
struct node
{
int x,cnt;//x为当前楼层，cnt记录次数
};
queue<node>q;
int main()
{
ans=-1;//若队列为空仍未搜索到终点，则ans=-1
cin>>n>>a>>b;
for(i=1;i<=n;i++)
cin>>k[i];
q.push({a,0});//先把起点入队
vis[a]=1;//标记起点已被访问
while(!q.empty())
{
node tmp=q.front();q.pop();//按队列顺序依次取出队首tmp
if(tmp.x==b){ans=tmp.cnt;break;}//找到终点，保存次数，结束搜索
newx=tmp.x+k[tmp.x];//上楼的情况
if(newx<=n&&vis[newx]==0)
{
vis[newx]=1;//标记已被访问
q.push({newx,tmp.cnt+1});//这里必须写cnt+1，写 ++cnt 和 cnt++ 都不行！
}
newx=tmp.x-k[tmp.x];//下楼的情况
if(newx>=1&&vis[newx]==0)
{
vis[newx]=1;//标记已被访问
q.push({newx,tmp.cnt+1});
}
}
printf("%d\n",ans);
return 0;
}
应该写了四五个小时吧，终于写完了，希望这篇博客能对你有所帮助~
京公网安备 11010502036488号