本文共 1461 字，大约阅读时间需要 4 分钟。

题意

类似皇后问题

思路

dfs，本题思路非常清晰了，唯一的问题是，怎么判断一个位置合法？

朴素的每一次标志防放置棋子的同行同列位置不合法是浪费严重的。

参考八皇后问题的优化，只需要标志一列是否放过即可(因为按行搜索不会出现一行放两个的问题)。

code

#include
   
    #define endl '\n'using namespace std;int n,k;char mp[10][10];int vis[10];int ans;void dfs(int t,int k){
       if(t==n+1||k==0){
           if(k==0) ++ans;        return;    }    dfs(t+1,k);    for(int i=1;i<=n;i++){
           if(mp[t][i]=='#'&&!vis[i]){
               vis[i]=1;            dfs(t+1,k-1);            vis[i]=0;        }    }    return;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n>>k){
           if(n==-1&&k==-1) break;        for(int i=1;i<=n;i++) cin>>(mp[i]+1);        ans=0;        dfs(1,k);        cout<
    
     <
    
   

ps:更新

#include
   
    #define endl '\n'using namespace std;int n,k;char mp[10][10];int vis[10];int ans;void dfs(int t){
       if(t==n+1||k==0){
           if(k==0) ++ans;        return;    }    for(int i=1;i<=n;i++){
           if(mp[t][i]=='#'&&!vis[i]){
               vis[i]=1; //之后不能再找这一列了            k--;      //放下一个棋子            dfs(t+1); //在这一行的某一列中有‘#’，直接转到下一行            vis[i]=0;  //取消标记方便下一次查找不同的方案            k++;        }    }    dfs(t+1); /如果上一行的列都没有‘#’，则换到下一行    return;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n>>k){
           if(n==-1&&k==-1) break;        for(int i=1;i<=n;i++) cin>>(mp[i]+1);        ans=0;        dfs(1);        cout<
    
     <
    
   

学如逆水行舟，不进则退

转载地址：http://iylbf.baihongyu.com/