BNUOJ 1440
这题其实就是变相的简单的n皇后问题,(不同的地方在于n皇后问题是每一行每一列都只摆放一个皇后,而这里可以不摆放)不过遍历时有个小技巧就是每走到一个位置都从此时的行出发往下遍历所有的行和列,这样,如果某一行不拜访,则可以通过循环直接下一行,无需再次递归,再次递归会TLE。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=100; int n,m,cnt; bool vis[maxn]; char g[10][10]; int dfs(int cur,int m){ if(m==0) return ++cnt; for(int i=cur;i<n;i++)///巧妙 for(int j=0;j<n;j++) if(g[i][j]=='#'&&!vis[j]){ vis[j]=true; dfs(i+1,m-1);///这里注意从i出发 vis[j]=false; } } int main(){ while(cin>>n){ cin>>m; if(m==-1&&n==-1) break; memset(g,'',sizeof(g)); memset(vis,0,sizeof(vis)); cnt=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ cin>>g[i][j]; //canf("%d",&g[i][j]); } dfs(0,m); cout<<cnt<<endl; } return 0; }
最后
以上就是高大雪糕最近收集整理的关于回溯水题训练的全部内容,更多相关回溯水题训练内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复