首页 > 代码库 > poj1321（棋盘问题）
poj1321（棋盘问题）
题目地址：棋盘问题
题目大意：
中文题。
解题思路：
深搜。数据很小，枚举每一行的棋盘“#”，然后往下一行深搜。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 int n,m; 44 char map[10][10]; 45 int p[10]; 46 int d,ce; 47 int maxx; 48 int DFS(int x,int y,int cnt) 49 { 50 int i,j,k; 51 if (cnt==m) 52 { 53 maxx++; 54 return 0; 55 } 56 for(i=x+1; i<n; i++) 57 for(j=0; j<n; j++) 58 { 59 ce=0; 60 if (map[i][j]==‘#‘) 61 { 62 for(k=0; k<d; k++) 63 if (p[k]==j) 64 ce=1; 65 if (ce) 66 continue; 67 p[d++]=j; 68 DFS(i,j,cnt+1); 69 d--; 70 p[d]=0; 71 } 72 } 73 return 0; 74 } 75 int main() 76 { 77 while(scanf("%d%d",&n,&m)!=EOF) 78 { 79 if (n==-1&&m==-1) 80 break; 81 int i,j; 82 memset(map,0,sizeof(map)); 83 memset(p,0,sizeof(p)); 84 for(i=0; i<n; i++) 85 scanf("%s",map[i]); 86 int cnt=0; 87 maxx=0; 88 for(i=0; i<n; i++) 89 for(d=0,ce=0,j=0; j<n; j++) 90 { 91 if (map[i][j]==‘#‘) 92 { 93 p[d++]=j; 94 DFS(i,j,cnt+1); 95 d--; 96 p[d]=0; 97 } 98 } 99 printf("%d\n",maxx);100 }101 return 0;102 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。