Java教程

DFS深度优先搜索

本文主要是介绍DFS深度优先搜索,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

(23条消息) DFS入门级(模板)_ღ江晚吟的博客-CSDN博客_dfs入门

思路:

  1. 所谓DFS就是指:优先考虑深度,换句话说就是一条路走到黑,直到无路可走的情况下,才会选择回头,然后重新选择一条路。
  2. 用book函数来存储是否走过一次,用a[step]来表示盒子,step为盒子的下标,i为扑克牌的面值
  3. 记得回溯操作
  4. 如果扑克牌没使用过(book[i]==0)就把它放进盒子里(a[step]=i),并把它的状态标记为1(book[i]=1),然后进行下一个盒子的操作(dfs(step+1)自我递归调用)
  5. 盒子里全部装满(step==n+1)表示一条路走完了,再开始走第二条路(,开始重新选择(DFS的思想),这里要注意的,不是把所有的牌都取出来重新放,这样就不符合DFS的思想了。)(return)直到全部走完

基本模型

void dfs(int step){

判断边界

尝试每一种可能 for(i=1;i<=n;i++){

继续下一步 dfs(step+1)

}

返回}

模板

假如有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。将这3张扑克牌分别放入3个盒子一共有几种不同的放法呢?

#include<bits/stdc++.h>
using namespace std;
long long book[100]={0};
long long a[100];
long long n;
void dfs(long long step)
{
    if(step==n+1)
    {
        for(int i=1;i<=n;i++)
        cout<<a[i];    
        cout<<endl;
        return;
    }

    for(int i=1;i<=n;i++)
    {
        if(book[i]==0)
        {
            book[i]=1;
            a[step]=i;
            dfs(step+1);
            book[i]=0;//回溯
        }
    }
    return;
}
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}

迷宫问题:

  1. 设step的初值是零更方便些
  2. a表示路况
  3. Book表示是否走过
  4. 路况不可改变,改变的是book的状态
  5. 用数组来模拟移动
#include<bits/stdc++.h>
using namespace std;
long long minn=999;
long long book[100][100]={0};
long long a[100][100];
long long m,n,s1,s2,e1,e2;
long long dir[4][2]={1,0,-1,0,0,1,0,-1};
long long cnt=0;
void dfs(long long x,long long y,long long step)
{
    if(x==e1&&y==e2)
    {
        if(step<minn)
        minn=step;
        //cout<<step<<endl;
        //cout<<minn<<endl;
        return;
    }
    for(int i=0;i<4;i++)
    {
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        //必须满足路况是0(可以走),而且状态是0 (没走过) 
        if(tx>=1&&tx<=m&&ty>=1&&ty<=n&&a[tx][ty]!=1&&book[tx][ty]!=1) 
        {
            book[tx][ty]=1;
            dfs(tx,ty,step+1);
            book[tx][ty]=0;
        }
        cnt++;
    }
    return;
}
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        cin>>a[i][j];
    }
    cin>>s1>>s2>>e1>>e2;
    a[s1][s2]=1;
    dfs(s1,s2,0);
    cout<<minn<<endl;
    //cout<<cnt<<endl;
    return 0;
}

简单的对以前在word中的算法笔记进行整理,自用,参考标注不完整,侵删

这篇关于DFS深度优先搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!