poj 1321 棋盘问题（dfs）

题目：http://poj.org/problem?id=1321

没什么难度，比较水。。。

View Code 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define pan(a,n) (a>=1&&a<=n) 5 using namespace std; 6 int n,k; 7 char str[10][10]; 8 int dire[4][2]={{1,0},{0,1}}; 9 int xvis[10],yvis[10]; 10 int num; 11 void dfs(int ax,int ay,int k) 12 { 13 if(k==0) 14 { 15 num++; 16 return ; 17 } 18 int i,j; 19 for(i=ax+1;i<=n;i++) 20 { 21 for(j=1;j<=n;j++) 22 { 23 if(str[i][j]=='#') 24 { 25 if(xvis[i]==0&&yvis[j]==0) 26 { 27 xvis[i]=1; 28 yvis[j]=1; 29 k--; 30 dfs(i,j,k); 31 k++; 32 xvis[i]=0; 33 yvis[j]=0; 34 } 35 } 36 } 37 } 38 } 39 int main() 40 { 41 int i,j; 42 while(scanf("%d%d",&n,&k)!=EOF) 43 { 44 if(n==-1&&k==-1) 45 break; 46 num=0; 47 memset(xvis,0,sizeof(xvis)); 48 memset(yvis,0,sizeof(yvis)); 49 for(i=1;i<=n;i++) 50 { 51 for(j=1;j<=n;j++) 52 { 53 cin>>str[i][j]; 54 } 55 } 56 for(i=1;i<=n;i++) 57 { 58 for(j=1;j<=n;j++) 59 { 60 if(str[i][j]=='#') 61 { 62 xvis[i]=1; 63 yvis[j]=1; 64 k--; 65 dfs(i,j,k); 66 k++; 67 xvis[i]=0; 68 yvis[j]=0; 69 } 70 } 71 } 72 cout<<num<<endl; 73 } 74 return 0; 75 }

 

转载于:https://www.cnblogs.com/wanglin2011/archive/2013/01/26/2877762.html

总结

以上是生活随笔为你收集整理的poj 1321 棋盘问题（dfs）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。