棋盘问题 poj1321

　　这道题就是简单的dfs，没错，我做了一个小时。

　　这道题就是给定一个棋盘，其中. 是空白的，不能放棋子，#是可以放棋子的位置。放棋子的时候，同一行同一列只能放一个棋子。

　　输入n,k

　　接着输入n*n的棋盘，#或者. ，求有多少种放棋子的方式。

··　　dfs（s,kk)表示目前放到了第几行，放了多少个棋子了。

　　当然，从dfs(0,0) 开始。

　　刚开始dfs(i+1,kk++1)写成了dfs(s+1,kk+1),然后一直tle。

 1 #include<cstdio>
 2 #include<cstring>
 3 char map[10][10];
 4 bool vis[10];
 5 int ans,k,n;
 6 void DFS(int s,int kk)
 7 {
 8     if(kk==k){
 9         ans++;
10         return ;
11     }
12     for(int i=s;i<n;i++){
13         for(int j=0;j<n;j++){
14             if(!vis[j]&&map[i][j]=='#'){
15                 vis[j]=true;
16                 DFS(i+1,kk+1);
17                 vis[j]=false;
18             }
19         }
20     }
21 }
22 int main()
23 {
24     while(scanf("%d%d",&n,&k)){
25         if(n==-1&&k==-1)
26             break;
27         for(int i=0;i<n;i++)
28             scanf("%s",map[i]);
29         memset(vis,false,sizeof(vis));
30         ans=0;
31         DFS(0,0);
32         printf("%d
",ans);
33     }
34     return 0;
35 }

View Code