|
目录
基本概念
算法思想
模板
例子
基本概念
深度优先搜索算法（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);
}
}
|