本文主要是介绍蓝桥杯算法基础(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+回溯+剪枝 -对这类问题的优化,使用剪枝,越早剪越好,但这很难 如 素数环
这篇关于蓝桥杯算法基础(34)深度优先搜索DFS(数独游戏)(部分和)(水洼数目)(八皇后问题)(素数环)(困难的串)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!