Java教程

深度优先搜索

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

深搜

推荐资料

1、一篇文章完全搞懂深度优先搜索(dfs)(含模板以及例题分析)

2、DFS模板

基本思路

一条路走到底,不能走就退回上一步,看看有没有别的分支可以走,不断的退回,选择分支。

大概结构

#include<bits/stdc++.h>
using namespace std;
int n, m;//n:有几个数  m:要几个 
bool used[ ];//是否用过 
int ans[ ];//答案 
void dfs(int u)
{
    if (出局判断)//到头就走 
    {
        做要做的事
        return ;//退出 
    }
    for (int i = 开始的地方; i <= n; i++)//从上一个数开始依次增加,枚举每一种情况 
    {
        if (used[i] == 0) //判断是否用过
        {
            加入结果 设为用过
            dfs(u + 1);//下一个数字 
            回溯:回到没用过
        }
    }
    return ;//退出 
}
int main()
{
    输入 初始化
    dfs(1);//开始搜索,从1开始 
    return 0;
}

样例代码:

P1434 滑雪

#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,a[201][201],s[201][201],ans;
bool use[201][201];
int dfs(int x,int y)
{
    if(s[x][y])
	{
		return s[x][y];
	}
    s[x][y]=1;
    for(int i=0;i<4;i++)
    {
	    int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy])
	    {
    		dfs(xx,yy);
            s[x][y]=max(s[x][y],s[xx][yy]+1);
	    }
    }
   return s[x][y];
}
int main()
{	
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
   	for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
       		
    }
    for(int i=1;i<=n;i++)
    {
   		for(int j=1;j<=m;j++)
   		{
		   ans=max(ans,dfs(i,j));
   		}
    }
    cout<<ans;
    return 0;
}
这篇关于深度优先搜索的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!