DFS经典例题（八皇后，数独）

1.1P1036 [NOIP 2002 普及组] 选数解题思路这里是组合思想与元素的排序无关列举出所有符合的组合再判断是否符合素数代码#includeiostreamusingnamespacestd;constintN21;inta[N];intpath;intret;intn,m;boolis(intpath){if(path1)returnfalse;for(inti2;ipath/i;i){if(path%i0){returnfalse;}}returntrue;}voiddfs(intpos,intbegin){if(posm){if(is(path)){ret;}return;}for(intibegin;in;i){patha[i];dfs(pos1,i1);path-a[i];}}intmain(){cinnm;for(inti1;in;i){cina[i];}dfs(1,1);coutret;return0;}1.2P9241 [蓝桥杯 2023 省 B] 飞机降落解题思路从数据范围上看只有1-10我们可考虑用深搜。eg:有三架飞机我们可以分成1,2,3 1,3,2 2,3,1 2,1,3 3,1,2 3,2,1六种情况这是全排列与元素的顺序有关。而且根据题目我们可以进行剪枝代码#includeiostream#includecstringusingnamespacestd;constintN11;intT[N],D[N],L[N];boolst[N];intt,n;intend,newend;booldfs(intpos,intend){if(posn){returntrue;}for(inti1;in;i){if(st[i]){continue;}if(endT[i]D[i]){continue;}st[i]true;newendmax(end,T[i])L[i];if(dfs(pos1,newend))returntrue;//有一个条件满足就返回st[i]false;}returnfalse;}intmain(){cint;while(t--){memset(st,0,sizeof(st));cinn;for(inti1;in;i){cinT[i]D[i]L[i];}if(dfs(1,0)){coutYESendl;}else{coutNOendl;}}return0;}1.3P1219 [USACO1.5] 八皇后 Checker Challenge解题思路列举出每种情况可以使用深搜但是根据题目中要求进行剪枝皇后不能放在同一列同一行正对角线副对角线上代码#includeiostream#includevectorusingnamespacestd;constintN14;vectorinta;intn;intret;boolcol[N],st1[N*2],st2[N*2];intp15;voiddfs(intx){if(xn){ret;if(ret3){for(autonum:a){coutnum ;}coutendl;}return;}for(inti1;in;i){//剪枝if(col[i]||st1[i-xp]||st2[ix]){continue;}a.push_back(i);col[i]st1[i-xp]st2[ix]true;dfs(x1);a.pop_back();col[i]st1[i-xp]st2[ix]false;}}intmain(){cinn;dfs(1);coutret;return0;}1.4P1784 数独解题思路暴搜一个一个格子去填从1-9开始开始合适的填进去再填下一个格子剪枝代码#includeiostreamusingnamespacestd;constintN11;inta[N][N];boolcol[N][N],row[N][N],st[N][N][N];intn8;booldfs(intx,inty){if(xn){returntrue;}if(yn){returndfs(x1,0);}if(a[x][y]){returndfs(x,y1);}for(inti1;i9;i){if(row[x][i]||col[y][i]||st[x/3][y/3][i]){continue;}a[x][y]i;row[x][i]col[y][i]st[x/3][y/3][i]true;if(dfs(x,y1))returntrue;row[x][i]col[y][i]st[x/3][y/3][i]false;a[x][y]0;}returnfalse;}intmain(){for(inti0;in;i){for(intj0;jn;j){cina[i][j];if(a[i][j]){row[i][a[i][j]]col[j][a[i][j]]st[i/3][j/3][a[i][j]]true;}}}if(dfs(0,0)){for(inti0;in;i){for(intj0;jn;j){couta[i][j] ;}coutendl;}}return0;}