蓝桥杯Java——DFS深度优先搜索算法_java dfs算法

目录

基本概念

算法思想

模板

例子

---

基本概念

深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

算法思想

沿着树的深度来遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

模板

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}   

例子

第13届蓝桥杯第1期上台阶

public class Main {
	private static int INF = 0x3f3f3f3f;
	static int a[] = {0,1,2,1,1,1,1,5,5,4,-1,-1,-2,-3,-1,-9};
	public static void main(String[] args) {
		dfs(0,0);
		System.out.println(dfs(0,0));
	}
	static int dfs(int idx, int k) {//idx是台阶数，k是步数
		if(idx == 15){
			return a[15];//最后一阶-9
		}
		if(k == 6) {//6步
			return -INF;
		}
		int ans = -INF;//得分
		for(int i=1;i <= 4 && idx + i <= 15;i++){
			ans = Math.max(ans, dfs(idx + i, k + 1));
		}
		return ans + a[idx];
	}
}

第11届蓝桥杯第1场分配口罩

法1

import java.util.Scanner;
 
public class Main{
    static int sum, cnt = 0x3f3f3f3f, value[] = new int[15];
//宏定义一个0x3f3f3f3f可以减少考虑的时间，一般情况下就可以当作是一个无穷大的数去用
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < 15; i++)
            sum += value[i] = in.nextInt();//口罩总数
        dfs(0, 0);
        System.out.print(cnt);//口罩之差
    }
 
    static void dfs(int d, int v) {//d是口罩批数，v是医院分得的口罩数
        if (d == 15) 
            cnt = min(cnt, abs(sum - v - v));//口罩之差
        else {
            dfs(d + 1, v + value[d]);
            dfs(d + 1, v);
        }
    }
 
    static int min(int a, int b) { return a < b? a: b; }
    static int abs(int a) { return a > 0? a: -a; }
}

法2

public class Main {
	public static long res=Long.MAX_VALUE;
	public static long num[]={9090400, 8499400, 5926800, 8547000, 4958200,
			   				  4422600, 5751200, 4175600, 6309600, 5865200, 
			   				  6604400, 4635000, 10663400, 8087200, 4554000
							}; 
    public static void main(String[] args){
    	dfs(0, 0, 0);
    	System.out.println(res);
	}
//k是口罩批数，sum1和sum2两家医院分得的口罩数
    public static void dfs(int k,long sum1,long sum2 ) {
    	if(k==15) {
    		res=res < Math.abs(sum1-sum2) ? res:Math.abs(sum1-sum2);
    		return;
    	}
    	dfs(k+1, sum1+num[k], sum2);
    	dfs(k+1, sum1, sum2+num[k]);
    }
}

第11届蓝桥杯第2场七段码

public class Main {
    public static int N=10;
    public static  int e[][]=new int[N][N];//存储二极管相邻的信息
    public static int f[]=new int[N];//并查集
    public static int ans=0;
    public static boolean st[]=new boolean[N];//true表示发光
    public static void init(){
        //表示相邻
        //1 2 3 4 5 6 7
        //a b c d e f g
        e[1][2]=e[1][6]=1;//a与b、f相邻
        e[2][1]=e[2][7]=e[2][3]=1;//b与a、g、c相邻
        e[3][2]=e[3][7]=e[3][4]=1;//c与b、g、d相邻
        e[4][3]=e[4][5]=1;//d与c、e相邻
        e[5][7]=e[5][6]=e[5][4]=1;//e与g、f、d相邻
        e[6][5]=e[6][7]=e[6][1]=1;//f与e、g、a相邻
        e[7][2]=e[7][3]=e[7][5]=e[7][6]=1;//g与b、c、e相邻
    }
 
    public static int find(int u){
        if(f[u]==u) return u;
        f[u]=find(f[u]);
        return f[u];
    }
 
    public static void dfs(int d){//1-7
        if(d>7){
            //终止条件
            for(int i=1;i<=7;i++){//并查集初始化
                f[i]=i;
            }
            for(int i=1;i<=7;i++){
                for(int j=1;j<=7;j++){
                    if(e[i][j]==1&&st[i]==true&&st[j]==true){//把所有发光且相邻的二极管合并
                        int fx=find(i),fy=find(j);
                        if(fx!=fy){
                            f[fx]=fy;//合并
                        }
                    }
 
                }
            }
            int k=0;//表示产生的集合的个数
            for(int i=1;i<=7;i++){
                if(st[i] &&f[i]==i)k++;
            }
            if(k==1) ans++;//只产生一个集合，说明所有的发光二极管是连成一片的
            return;
        }
 
        st[d]=true;
        dfs(d+1);
        st[d]=false;
        dfs(d+1);
    }
 
    public static void main(String[] args) {
        init();
        dfs(1);
        System.out.println(ans);
    }
}