poj1321-棋盘问题（深搜）

Love The Way You Lie 2022-06-09 04:09 179阅读 0赞

![Image 1][]

![Image 1][]

思路：用深搜， 注意有两个终止条件。一个是棋盘的范围， 一个是棋子的数量。但是注意棋子的判断要在棋盘的前面。因为可能这一次的搜索超出了棋盘， 但是这一次也刚好是棋子的数量。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10;
    const int INF=0x3f3f3f3f; 
    int row[maxn], cnt, num;
    int n, k;
    char  mp[maxn][maxn];
    
    void dfs(int col)
    {
    	if(num==k)
    	{
    		cnt++;
    		return;
    	}
    	if(col>n)
    		return;
    	for(int i=1; i<=n; i++)
    	{
    		if(!row[i] && mp[i][col]=='#')
    		{
    			row[i]=1; 
    			num++;
    			dfs(col+1);
    			row[i]=0;
    			num--;
    		}
    	}
    	dfs(col+1);
    	return;
    }
    
    int main(){
    	while(cin>>n>>k && (n!=-1 && k!=-1))
    	{
    		cnt=num=0;
    		memset(row, 0, sizeof(row));
    		for(int i=1; i<=n; i++)
    		{
    			for(int j=1; j<=n; j++)
    			{
    				cin>>mp[i][j];
    			}	
    		}
    		
    		dfs(1);
    		cout<<cnt<<endl;	
    	}
    	return 0;
    }

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关算法提高棋盘多项式（深搜）

问题描述　　八皇后问题是在棋盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得换

蔚落/ 2022年09月30日 10:55/ 0 赞/ 162 阅读

相关 POJ 1321-棋盘问题【简单搜索】

棋盘问题 <table style="text-align:center"> <tbody> <tr> <td><strong>Time Limit:</s

ゝ一纸荒年。/ 2022年08月19日 08:51/ 0 赞/ 165 阅读

相关 poj 1321 棋盘问题 dfs暴力

棋盘问题 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td> <td

淡淡的烟草味﹌/ 2022年08月18日 11:57/ 0 赞/ 179 阅读

相关 pku 1321 棋盘问题简单DFS

\include <iostream> using namespace std; int map\[8\]\[8\]; int visited\[8\]\[8\]; int N

女爷i/ 2022年08月09日 15:59/ 0 赞/ 179 阅读

相关 poj 1321棋盘问题

递归实现深搜（Dfs） \[poj 1321\] ([http://poj.org/problem?id=1321][http_poj.org_problem_id_132

布满荆棘的人生/ 2022年08月08日 15:52/ 0 赞/ 192 阅读

相关 POJ 1321 棋盘问题

> 棋盘问题 > Time Limit: 1000MS Memory Limit: 10000K > Total Submissions: 43158 Accepted

雨点打透心脏的1/2处/ 2022年06月18日 09:18/ 0 赞/ 203 阅读

相关 poj-1321-棋盘问题（深搜）

棋盘问题 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

我不是女神ヾ/ 2022年06月12日 11:39/ 0 赞/ 165 阅读

相关 poj1321-棋盘问题（深搜）

![Image 1][] ![Image 1][] 思路：用深搜，注意有两个终止条件。一个是棋盘的范围，一个是棋子的数量。但是注意棋子的判断要在棋盘的前面。因为可

Love The Way You Lie/ 2022年06月09日 04:09/ 0 赞/ 180 阅读

相关 POJ 1321 棋盘问题 (N皇后变形)

题意：在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k

刺骨的言语ヽ痛彻心扉/ 2022年05月19日 14:34/ 0 赞/ 176 阅读

相关 POJ 1321 棋盘问题(DFS板子题，简单搜索练习)

棋盘问题 <table> <tbody> <tr> <td> <strong>Time Limit:</strong> 1000MS</td>

待我称王封你为后i/ 2022年02月01日 09:19/ 0 赞/ 209 阅读