搜索 有状态约束的 问题
1.POJ-1321
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<string.h> 5 #include<cstdio> 6 using namespace std; 7 #define maxn 1000 8 char a[10][10]; 9 int vis[10]; 10 int n,k,m; 11 long long cnt=0; 12 void dfs(int x)//按行遍历 13 { 14 if(m==k) 15 { 16 cnt++; 17 return; 18 } 19 if(x>=n) 20 return ; 21 for(int i=0;i<n;i++) 22 { 23 if(a[x][i]==‘#‘&&vis[i]==0) 24 { 25 vis[i]=1; 26 m++; 27 dfs(x+1); 28 vis[i]=0; 29 m--; 30 } 31 } 32 dfs(x+1); 33 } 34 int main() 35 { 36 while(cin>>n>>k) 37 { 38 if(n==-1&&k==-1) 39 break; 40 cnt=0,m=0; 41 memset(vis,0,sizeof(vis)); 42 for(int i=0;i<n;i++) 43 scanf("%s",&a[i]); 44 dfs(0); 45 cout<<cnt<<endl; 46 } 47 }
方法二：
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<string.h> 5 #include<cstdio> 6 using namespace std; 7 int n,k,cnt=0,m; 8 char a[10][10]; 9 int vis[10]; 10 void dfs(int x) 11 { 12 if(m==k) 13 { 14 cnt++; 15 return; 16 } 17 if(x>=n) 18 return; 19 for(int j=x;j<n;j++) 20 for(int i=0;i<n;i++) 21 { 22 if(a[j][i]==‘#‘&&vis[i]==0) 23 { 24 vis[i]=1; 25 m++; 26 dfs(x+1); 27 m--; 28 vis[i]=0; 29 } 30 } 31 } 32 int main() 33 { 34 while(cin>>n>>k) 35 { 36 cnt=0,m=0; 37 memset(vis,0,sizeof(vis)); 38 if(n==-1&&k==-1) 39 break; 40 for(int i=0;i<n;i++) 41 scanf("%s",&a[i]); 42 dfs(0); 43 cout<<cnt<<endl; 44 } 45 }
二：连通性问题：
1.判断连通块数量问题
http://ybt.ssoier.cn:8088/problem_show.php?pid=1335
3 3 1 1 1 0 1 0 1 0 1
3
分析：如图三个连通块表示分别用三个颜色表示
1 1 1 0 1 0 1 0 1
原文：https://www.cnblogs.com/Aiahtwo/p/11035840.html