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

深度优先搜索DFS
Depth First Searchdfs:先把一条路走到黑
纵横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=4a={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);//清除一个水洼//计数加1cnt++;//清楚之后，就继续找下一个水洼}}}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 1for(int l=-1;k<2'k++){//-1 0 1if(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小于等于15int 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的话，输出ABACA,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+回溯+剪枝
-对这类问题的优化，使用剪枝，越早剪越好，但这很难
如 素数环