蓝桥杯算法基础（34）深度优先搜索DFS（数独游戏）（部分和）（水洼数目）（八皇后问题）（素数环）（困难的串）

深度优先搜索DFS
Depth First Search

dfs:先把一条路走到黑
纵横


bfs:所有路口看一遍
图
必须借助队列的数据结构


无死角搜索

数独游戏

你一定听说过数独游戏
如下图所示，玩家需要根据9*9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行，每一列，每一个同色九宫内的数字均含1~9，不重复。
数独的答案都是第一的，所以，多个阶解也称为无解
本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目，但对会使用计算机编程的你来说，恐怕易如反掌了。
本题的要求就是输入数独题目，程序输出数独的唯一解，我们保证所有已知数据的格式都是合法的，并且题目有唯一的解
格式要求，输入9行，每行9个数字，0代表未知，其他数字为已知
输出9行，每行9个数字代表数独的解
输入:

005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700

程序应该输出:


//这道题有为一街
dfs(table,x,y){
    if(x==9){
        print(table);
        System.exit(0);
  }
    if(table[x][y]=='0'){
    //选1~9之间合法的数字到x,y这个位置
        for(i=1..9){
           boolean res=check(table,x,y,i);
            if(res){
            table[x][y]=(char)('0'+i);//转移到下一个状态
            dfs(table,x+(y+1)/9,(y+1)%9);//当y等于8的时候，x+1,因为x,y的位置是从0开始的，一行行的走
            }
        }
        //循环结束，进行回溯
        table[x][y]=0;
    }else{
     //继续找下一个需要处理的位置
        dfs(table,x+(y+1)/9,(y+1)%9);
    }
}



public static void main(String args){

    Scanner sc=new Scanner(System.in);
    char[][] table=new char[9][];
    for(int i=0;i<9;i++){
        table[i]=sc.nextLine().toCharArray();//输入字符串，然后转成数组

    }
    dfs(table,0,0);


}

    private static void dfs(char[][] table,int x,int y){
        if(x==9){//8是最大，当为9时，则意味着数组以填满
            print(table);
            System.exit(0);
        }

        if(table[x][y]=='0'){//虚位以待

            for(int k=0;K<10;k++){
                if(check(table,x,y)){
                    table[x][y]=(char)('0'+k);
                    dfs(table,x+(y+1)/9,(y+1)%9,k);//处理下一个状态
                }
                table[x][y]='0';//回溯

            }else{
            dfs(table,x+(y+1)/9,(y+1)%9);//处理下一个状态

            }
        }



    }



private static boolean check(char[][] table,int i,int j,int k){
        for(int i=0;i<9;i++){
        System.out.println(new String(table[i]));
        }

}

    private static boolean check(char[][] table,int i,int l,int k){
    //检查同行和同列
    for(int l=0;l<9;l++){
        if(table[i][l]==(char)('0'+k))return false;
        if(table[l][j]==(char)('0'+k))retrun false;

    }
    //检查小九宫格
    for(int l=(i/3)*3;l<(i/3+1)*3;l++){
        for(int m=(j/3)*3;m<(j/3+1)*3;m++){
            if(table[l][m]==(char)('0'+k))return false;
        }

    }
    }


//m=(j/3)*3;m<(j/3+1)*3
(j/3)*3假设j为8，(j/3)前面有几个九宫格数，(j/3)*3直接回到当前九宫格最开始的位置
(j/3+1)为之前的九宫格数再加1个九宫格，(j/3+1)*3便来到当前九宫格宫格下一个九宫格的开始位置，即到这里结束
[*][] [] [*][] [] [*][] []
[] [] [] [] [] [] [] [] []
[] [] [] [] [] [] [] [] []
[*][] [] [*][] [] [*][] []
[] [] [] [] [] [] [] [] []
[] [] [] [] [] [] [] [] []
[*][] [] [*][] [] [*][] []
[] [] [] [] [] [] [] [] []
[] [] [] [] [] [] [] [] []

部分和

给定整数序列a1,a2,....,an,判断是否可以从中选出若干数，使他们和恰好为k;

    1<=20
    -10^8<ai<10^8

    -10^8<k<10^8

输入:
    n=4
    a={1,2,4,7};
    k=13
输出:
        Yes(13=2+4+7);

老思想，选与不选的问题

private static void dfs(int[] a,int k,int cur,ArrayList<Integer> ints){
    if(k==0){
    System.out.println("Yes ("+kk+" = ");//kk=原始的数
    int size=ints.size();
    for(int i=0;i<size;i++){
        System.out.println(ints.gets(i)+(i==size-1?"":" + "));//不要最后一个"+"
    }
    System.exit(0);
    }

    if(k<||cur==a.length)return;
    if(k==0){

    }

    dfs(a,k,cur+1,ints);//不要cur这个元素
    ints.add(a[cur]);
    int index=ints.size()-1;
    dfs(a,k-a[cur],cur-1,ints);//要cur这个元素
    ints.remove(index);//回溯
}

水洼数目

有一个大小为N*M的园子，雨后积起了水。八联通的积水被认为是连在一起的，请求出园子里总共有多少水洼?
(八连通指的是下图中相对w的*部分)

∗∗∗
∗W∗
∗∗∗


10 12
W********WW*
*WWW*****WWW
****WW***WW*
*********WW*
*********W**
**W******W**
*W*W*****WW*
W*W*W*****W*
*W*W******W*
**W*******W*



八连通问题
以一个W的位置为起点，找到所有的与W相连的W，每个W都有8个方向，连通在一起为一块水洼，找一共有几个水洼
走到一个位置，就将水抽掉，w->*,知道所有的水都走完

    public static void main(String[] args){
     Scanner sc=new Scanner(Systemn.in);
           int N=sc.nextInt();

           intM=sc.nextInt();
          char[][] a=new char[N][];
          for(int i=0;i<N;i++){
            a[i]=sc.nextLine().toCharArray();
          }
        int cnt;
          for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(a[i][j]=='W'){
                    dfs(a,i,j);
                    //清除一个水洼
                    //计数加1

                    cnt++;
                    //清楚之后，就继续找下一个水洼
                }
            }
          }


          System.out.println(cnt);
    }

    private static void dfs(char[][] a,int i,int j){
        a[i][j]='.';
  //        if(i>0&&a[i-1][j]=='w')dfs(a,i-1;j);

    //      if(i<a.length-1&&a[i+1][j]=='w')dfs(a,i+1;j);

      //    if(j>0&&a[i][j-1]=='w')dfs(a,i;j-1);

        //  if(j<a[0].length-1&&a[i][j+1]=='w')dfs(a,i;j+1);

//          if(i>0&&j>0&&a[i-1][j-1]=='w')dfs(a,i-1;j-1);

  //        if(i>0&&j<a[0].length-1&&a[i-1][j+1]=='w')dfs(a,i-1;j+1);

    //      if(i<a.length-1&&j>0&&a[i+1][j-1]=='w')dfs(a,i+1;j-1);

      //    if(i<a.length-1&&j<a[0].length&&a[i+1][j+1]=='w')dfs(a,i+1;j+1);



 //用循环来表示8个方向
        for(int k=-1;k<2;k++){//-1 0 1
            for(int l=-1;k<2'k++){//-1 0 1
                if(k==0&&l==0)continue;
                //8个方向，自身跳过
                if(i+k>=0&&i+k<=n-1&&j+l>=0&&j+l<=m-1){
                    if(a[i+k][j+l]=='w')
                    dfs(a,i+k,j+l);
                }

            }
        }

    }

八皇后问题

回溯和剪枝

回溯
-递归调用代表开启一个分支，如果希望这个分支返回后某些数据恢复到分支
开启前的状态，以便”重新开始“，就要使用回溯技巧
-全排列的”交换法，数独，部分和“，用到了回溯
剪枝
-深搜时，如已明确从当前状态无论如何转移都不会存在（更优）解，就应该中断往下的继续搜索，这种方法称为剪枝
-“数独”里面有剪枝
-“部分和”里面有剪枝
        if(限定)
        dfs
请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子
使得每行每列和每条对角线上都只有棋子，求其拜访的方法数。

给定一个int n，请返回方法数，保证n小于等于15



int n;
int[] rec;
int cnt;

dfs(l);

dfs(row){
       if(rec[row]==n+1){//越界后，意味着每一行都找完了
       cnt++;//找到一个
       return;
       }

    for(col from 1 to n){
        if(check(rec,row,col))
        rec[row]=col;
        dfs(rec,row+1);
        rec[row]=0;

    }

}

//x-y相同，主对角线
//x+y相同, 副对角线
check(rec,x,y){
    for(int i=0;i<rec.length;i++){
    //因为它每一行只选一个，所以不用判断横坐标
        if(rec[i]==y){//不能与rec数组中元素的y相同，即不能在同一列
            return false;
        }
        if(i+rec[i]==x+y)[//副对角线
            return false;
        }
        if(i-rec[i]==x-y){//主对角线
        return false;
        }
    }
    return true;
}



public class Dfs_n皇后问题{

        int n;
        int count;

        int[] vis;
        public static void main(String[] agrs){
        n=4;
      、
        rec=new int[4];

        dfs(0);
        System.out.println(cnt);
        }

        private static void dfs(int row){
            if(row==n){
            cnt++;
            return;
            }
            //依此尝试在某列上放一个皇后
            for(int col=0;col<n;col++){
            boolean ok=true;//先从第一行开始

            for(int i=0;i<row;i++){

                if(rec[i]==col||i+rec[i]==row+col||row[i]-i==col-row){
                        ok=false;
                        break;//这一行的着一列不能放
                }


            }

            //这里可以认为是一个剪枝
            //从这一行的这一列可以放
            if(ok){
            rec[row]=col;//标记
            dfs(row+1);//继续找下一行
                //rec[row]=0;//恢复原状，这种解法这里是否恢复状态都行，为什么?
                //因为当前数组的长度不是rec数组的最大长度，而是依靠变化的row参数来递增和回溯的，即使当前row的后面有元素，也不必管他，只需要关注0~row之内的就行了
            }


            }


        }


}

素数环

输入正整数n,对1~n进行排列，便得相邻两个数之和均为素数
输出时从整数1开始，逆时针排序，同一个环应恰好输出一次

n<=16

如输出:6
输出:
1 4 3 2 5 6
1 6 5 2 3 4

//伪代码
int[] rec=new int[n];
rec[0]=1;
dfs(k){
    if(k==n){
    print(rec);
 return rec;
    }

    for(i from 2 to n){
        if(check(rec,i)){//1.i中没有在rec中出现过，2.i+rec[k-1]是一个素数

            rec[k]=i;
            dfs(k+1);
            rec[k]=0;

        }
    }

}

private static void dfs(int n,int[] r,int cur){
    if(cur==n&&isP(r[0]+r[n+1])){//填到末尾，还有首尾相加为素数才算成功
    print(r);
    return;
    }

    for(int 2;i<=n;i++){//尝试用每个数字填到cur这个位置上
        if(check(r,i,cur)){//r中没有这个数，且和上一个数之和为素数
            r[cur]=i;//试着将i放在cur位置,往前走一步
            dfs(n,r,cur+1);
              r[cur]=0;//回溯
        }

    }

}

private static boolean isP(int k){
    for(int i=2;i*i<=k;i++){
        if(k%i==0)return false;

    }
    return true;

}

困难的串

问题描述:如果一个字符串包括两个相邻的重复子串，则称他为容易的串，其他串称为困难的串
如:BB,ABCDACABCAB,ABCDABCD都是容易的，A,AB,ABA,D,DC,ABDAB,CBABCBA都是困难的。

输入正整数n，L,输出由前L个字符(大写英文字母)组成的，字典序第n小的困难的串
例如，当L=3时，前7个困难的串分别为:
A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA
n指定为4的话，输出ABAC

A,AB,ABA,ABAC,ABACA,//ABACB这个不行，因为是根据字典序来排的，ABACAB比ABACB字典序要小

是困难串就在后面加后缀

private static void dfs(int l,int n,String prefix){

            //尝试在prefix后追加一个字符
            for(char i='A';i<'A'+l;i++){
                if(isHard(prefix,i)){//是困难的串，就组合起来输出
                    String x=prefix+i;
                   System.out.println(x);
                   count++;//计数
                   if(count==n)
                 System.exit(0);
                 dfs(l,n,x);
                }

            }
}

private static boolean isHard(String prefix,char i){
        int count=0;//截取的宽度
        for(int j=prefix.length()-1;j>=0;j-=2){
            final String s1=prefix.substring(j,j+count+1);//从最后一个开始，随着j的往后移动，count也在逐渐增加
            final String s2=prefix.substring(j+count+1)+i; //j是两个两个的减，count一个一个的加，从新加入的字符的地方开始，先判断一个与一个判断是否相等，再两个两个，最后一半一半
                    if(s1.equals(s2))
                    return false;
                    count++;
        }
    return true;
}

小结
-有一类问题，有明确的的递归形式，比较容易用迭代形式实现，用递归也有比较明确的层数和宽度
走楼梯，走方格，硬币表示，括号组合，子集，全排列
-有一类问题，解的空间很大(往往是阶乘级别的)，要在所有可能性中找到答案，只能进行试探，尝试往前走一步,走不通在退回来，这就是dfs+回溯+剪枝
-对这类问题的优化，使用剪枝，越早剪越好，但这很难
如 素数环