设为首页 加入收藏

TOP

kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321
2019-07-10 16:11:12 】 浏览:16
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专题 专题一 简单搜索 Pr.. 下一篇洛古最简单50题解(41-50)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }