注意事项:
- 如果在回溯法中修改了全局变量,除非特殊需要,要及时把他恢复原样 ,若函数有多个出口,一定要在每个出口出恢复哦。
- 注意有些题目的特殊需要(如:素数环中判断第一个和最后一个,别忘了哦)。
- 要避免不必要的判断: 前面的已经判断过了后,回溯时就不需要判断了(除非特殊,看情况吧)。
回溯技巧(应该可以用在其他搜索上) : 剪枝
典型例题:
八皇后:
https://www.luogu.org/problemnew/show/P1219
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,tot,tmp; 5 int vis[3][200];//用数组判断在当前行能不能放皇后; 6 //提高效率 7 int ans[13+9];//用于打印 (注:答案在ans[0] ~ ans[n-1] 中哦 8 9 void print_ans() { 10 for(int i = 0; i < n; i++) 11 { 12 printf("%d ",ans[i]+1);//这个+1没啥别的意思,就是我做的那题是从一开始的 13 } 14 printf("\n"); 15 return ; 16 } 17 18 void dfs(int cur) { //参数是已搜到的层数 19 if(cur == n) { 20 tot++; 21 tmp++; 22 if(tmp <= 3) print_ans();//...... 23 } 24 else for(int i = 0; i < n; i++) { 25 if(!vis[0][i] && !vis[1][i+cur] && !vis[2][i-cur+n]) { 26 //列 x+y主对角线 x-y副对角线 上都没有皇后 注:副对角线相减有负的 27 vis[0][i] = vis[1][i+cur] = vis[2][i-cur+n] = 1;//标记已访问 28 ans[cur] = i; 29 dfs(cur+1); 30 vis[0][i] = vis[1][i+cur] = vis[2][i-cur+n] = 0;//回溯 31 } 32 } 33 34 } 35 36 int main() { 37 scanf("%d",&n); 38 dfs(0);//一层都没搜到,所以是0 39 printf("%d",tot); 40 return 0; 41 }