kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321

 

题目链接：https://vjudge.net/problem/poj-1321

 

题意：给一张棋盘，‘#’表示可以下棋的地方，‘.’表示不能下棋的地方。
棋盘是n*n的，要求能放下k个棋子，要求k个棋子在不同行不同列

思路：dfs，首先遍历地图找到第一个可以下棋的地方，然后从下一行开始继续dfs，如果已下棋子数等于要求棋子数，答案++

---

 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 }