c/c++语言开发共享kuangbin专题 专题一 简单搜索 棋盘问题 POJ – 1321

 1 #include <iostream>   2 #include <string.h>   3 #include <algorithm>   4 using namespace std;   5    6 #define rep(i,j,k) for(int i = (j); i <= (k); i++)   7 #define per(i,j,k) for(int i = (j); i >= (k); i--)   8    9 const int n = 15;  10 char mp[n][n];  11 bool vis[n];//记录列是否下的情况，可以看看紫书上八皇后的讲解  12 int ans;  13 int n,k;  14   15 void input(){  16   17     rep(i, 1, n){  18         rep(j, 1, n) cin >> mp[i][j];  19     }  20 }  21   22 void init(){  23     memset(vis, 0, sizeof(vis));  24     ans = 0;  25 }  26   27 void dfs(int cur,int chess){  28   29     rep(i, cur, n){  30         if (!(n - i >= k - chess)) continue;//如果剩余行数小于了剩余还要下的棋子数，说明  31                                             //棋子无法完全下完直接忽略  32   33         rep(j, 1, n){  34   35             if (vis[j] || mp[i][j] == '.') continue;//在这个dfs分支中j列已经有棋子  36                                                     //或者该空间无法下棋子  37   38             if (chess == k) { ans++; continue; } //棋子数满足了，ans++  39   40             vis[j] = true;//标记该dfs分支j列有棋子  41             dfs(i + 1,chess + 1);  42             vis[j] = false;//回溯  43         }  44     }  45 }  46   47   48 int main(){  49   50     ios::sync_with_stdio(false);  51     cin.tie(0);  52   53     while (cin >> n >> k){  54         if (n == -1 && k == -1) break;  55   56         init();  57         input();  58         dfs(1,1);  59   60         cout << ans << endl;  61     }  62   63   64     return 0;  65 }