三大框架对网站开发的作用,内部网站搭建,哈尔滨网站建设与管理,在阿里云上建立网站的步骤深度优先搜索DFS
Depth First Searchdfs:先把一条路走到黑
纵横bfs:所有路口看一遍
图
必须借助队列的数据结构无死角搜索数独游戏 你一定听说过数独游戏
如下图所示#xff0c;玩家需要根据9*9盘面上的已知数字#xff0c;推理出所有剩余空格的数字#xff0c;并满足每一行…深度优先搜索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(x9){print(table);System.exit(0);}if(table[x][y]0){//选1~9之间合法的数字到x,y这个位置for(i1..9){boolean rescheck(table,x,y,i);if(res){table[x][y](char)(0i);//转移到下一个状态dfs(table,x(y1)/9,(y1)%9);//当y等于8的时候x1,因为x,y的位置是从0开始的一行行的走}}//循环结束进行回溯table[x][y]0;}else{//继续找下一个需要处理的位置dfs(table,x(y1)/9,(y1)%9);}
}public static void main(String args){Scanner scnew Scanner(System.in);char[][] tablenew char[9][];for(int i0;i9;i){table[i]sc.nextLine().toCharArray();//输入字符串然后转成数组}dfs(table,0,0);}private static void dfs(char[][] table,int x,int y){if(x9){//8是最大当为9时则意味着数组以填满print(table);System.exit(0);}if(table[x][y]0){//虚位以待for(int k0;K10;k){if(check(table,x,y)){table[x][y](char)(0k);dfs(table,x(y1)/9,(y1)%9,k);//处理下一个状态}table[x][y]0;//回溯}else{dfs(table,x(y1)/9,(y1)%9);//处理下一个状态}}}private static boolean check(char[][] table,int i,int j,int k){for(int i0;i9;i){System.out.println(new String(table[i]));}}private static boolean check(char[][] table,int i,int l,int k){//检查同行和同列for(int l0;l9;l){if(table[i][l](char)(0k))return false;if(table[l][j](char)(0k))retrun false;}//检查小九宫格for(int l(i/3)*3;l(i/31)*3;l){for(int m(j/3)*3;m(j/31)*3;m){if(table[l][m](char)(0k))return false;}}}//m(j/3)*3;m(j/31)*3
(j/3)*3假设j为8(j/3)前面有几个九宫格数(j/3)*3直接回到当前九宫格最开始的位置
(j/31)为之前的九宫格数再加1个九宫格(j/31)*3便来到当前九宫格宫格下一个九宫格的开始位置即到这里结束
[*][] [] [*][] [] [*][] []
[] [] [] [] [] [] [] [] []
[] [] [] [] [] [] [] [] []
[*][] [] [*][] [] [*][] []
[] [] [] [] [] [] [] [] []
[] [] [] [] [] [] [] [] []
[*][] [] [*][] [] [*][] []
[] [] [] [] [] [] [] [] []
[] [] [] [] [] [] [] [] [] 部分和 给定整数序列a1,a2,....,an,判断是否可以从中选出若干数使他们和恰好为k;120-10^8ai10^8-10^8k10^8输入:n4a{1,2,4,7};k13
输出:Yes(13247);老思想选与不选的问题private static void dfs(int[] a,int k,int cur,ArrayListInteger ints){if(k0){System.out.println(Yes (kk );//kk原始的数int sizeints.size();for(int i0;isize;i){System.out.println(ints.gets(i)(isize-1?: ));//不要最后一个}System.exit(0);}if(k||cura.length)return;if(k0){}dfs(a,k,cur1,ints);//不要cur这个元素ints.add(a[cur]);int indexints.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 scnew Scanner(Systemn.in);int Nsc.nextInt();intMsc.nextInt();char[][] anew char[N][];for(int i0;iN;i){a[i]sc.nextLine().toCharArray();}int cnt;for(int i0;iN;i){for(int j0;jM;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(i0a[i-1][j]w)dfs(a,i-1;j);// if(ia.length-1a[i1][j]w)dfs(a,i1;j);// if(j0a[i][j-1]w)dfs(a,i;j-1);// if(ja[0].length-1a[i][j1]w)dfs(a,i;j1);// if(i0j0a[i-1][j-1]w)dfs(a,i-1;j-1);// if(i0ja[0].length-1a[i-1][j1]w)dfs(a,i-1;j1);// if(ia.length-1j0a[i1][j-1]w)dfs(a,i1;j-1);// if(ia.length-1ja[0].lengtha[i1][j1]w)dfs(a,i1;j1);//用循环来表示8个方向for(int k-1;k2;k){//-1 0 1for(int l-1;k2k){//-1 0 1if(k0l0)continue;//8个方向自身跳过if(ik0ikn-1jl0jlm-1){if(a[ik][jl]w)dfs(a,ik,jl);}}}} 八皇后问题 回溯和剪枝回溯
-递归调用代表开启一个分支如果希望这个分支返回后某些数据恢复到分支
开启前的状态以便”重新开始“就要使用回溯技巧
-全排列的”交换法数独部分和“用到了回溯
剪枝
-深搜时如已明确从当前状态无论如何转移都不会存在更优解就应该中断往下的继续搜索这种方法称为剪枝
-“数独”里面有剪枝
-“部分和”里面有剪枝if(限定)dfs
请设计一种算法解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子
使得每行每列和每条对角线上都只有棋子求其拜访的方法数。给定一个int n请返回方法数保证n小于等于15int n;
int[] rec;
int cnt;dfs(l);dfs(row){if(rec[row]n1){//越界后意味着每一行都找完了cnt;//找到一个return;}for(col from 1 to n){if(check(rec,row,col))rec[row]col;dfs(rec,row1);rec[row]0;}}//x-y相同主对角线
//xy相同, 副对角线
check(rec,x,y){for(int i0;irec.length;i){//因为它每一行只选一个所以不用判断横坐标if(rec[i]y){//不能与rec数组中元素的y相同即不能在同一列return false;}if(irec[i]xy)[//副对角线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){n4;、recnew int[4];dfs(0);System.out.println(cnt);}private static void dfs(int row){if(rown){cnt;return;}//依此尝试在某列上放一个皇后for(int col0;coln;col){boolean oktrue;//先从第一行开始for(int i0;irow;i){if(rec[i]col||irec[i]rowcol||row[i]-icol-row){okfalse;break;//这一行的着一列不能放}}//这里可以认为是一个剪枝//从这一行的这一列可以放if(ok){rec[row]col;//标记dfs(row1);//继续找下一行//rec[row]0;//恢复原状这种解法这里是否恢复状态都行为什么?//因为当前数组的长度不是rec数组的最大长度而是依靠变化的row参数来递增和回溯的即使当前row的后面有元素也不必管他只需要关注0~row之内的就行了}}}} 素数环 输入正整数n,对1~n进行排列便得相邻两个数之和均为素数
输出时从整数1开始逆时针排序同一个环应恰好输出一次n16如输出:6
输出:
1 4 3 2 5 6
1 6 5 2 3 4//伪代码
int[] recnew int[n];
rec[0]1;
dfs(k){if(kn){print(rec);return rec;}for(i from 2 to n){if(check(rec,i)){//1.i中没有在rec中出现过2.irec[k-1]是一个素数rec[k]i;dfs(k1);rec[k]0;}}}private static void dfs(int n,int[] r,int cur){if(curnisP(r[0]r[n1])){//填到末尾还有首尾相加为素数才算成功print(r);return;}for(int 2;in;i){//尝试用每个数字填到cur这个位置上if(check(r,i,cur)){//r中没有这个数且和上一个数之和为素数r[cur]i;//试着将i放在cur位置,往前走一步dfs(n,r,cur1);r[cur]0;//回溯}}}private static boolean isP(int k){for(int i2;i*ik;i){if(k%i0)return false;}return true;} 困难的串 问题描述:如果一个字符串包括两个相邻的重复子串则称他为容易的串其他串称为困难的串
如:BB,ABCDACABCAB,ABCDABCD都是容易的A,AB,ABA,D,DC,ABDAB,CBABCBA都是困难的。输入正整数nL,输出由前L个字符(大写英文字母)组成的字典序第n小的困难的串
例如当L3时前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 iA;iAl;i){if(isHard(prefix,i)){//是困难的串就组合起来输出String xprefixi;System.out.println(x);count;//计数if(countn)System.exit(0);dfs(l,n,x);}}
}private static boolean isHard(String prefix,char i){int count0;//截取的宽度for(int jprefix.length()-1;j0;j-2){final String s1prefix.substring(j,jcount1);//从最后一个开始随着j的往后移动count也在逐渐增加final String s2prefix.substring(jcount1)i; //j是两个两个的减count一个一个的加从新加入的字符的地方开始先判断一个与一个判断是否相等再两个两个最后一半一半if(s1.equals(s2))return false;count;}return true;
}小结
-有一类问题有明确的的递归形式比较容易用迭代形式实现用递归也有比较明确的层数和宽度
走楼梯走方格硬币表示括号组合子集全排列
-有一类问题解的空间很大(往往是阶乘级别的)要在所有可能性中找到答案只能进行试探尝试往前走一步,走不通在退回来这就是dfs回溯剪枝
-对这类问题的优化使用剪枝越早剪越好但这很难
如 素数环
