TOP

kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321
2019-07-10 16:11:12 】 浏览:58
Tags: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 }

 


kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321 https://www.cppentry.com/bencandy.php?fid=49&id=227471

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇kuangbin专题 专题一 简单搜索 Pr.. 下一篇洛古最简单50题解(41-50)