棋盘问题（dfs，递归）

﹏ヽ暗。殇╰゛Y 2022-12-04 09:15 187阅读 0赞

按照行的顺序遍历，其中dfs(int x,int count)表示第x行已放置count个棋子状态下遍历放置的过程。需要注意的是for循环之后必须要加上一个dfs因为不能保障每一行都可已找到一个可以放下的位置。

#include<stdio.h>
    #include<iostream>
    using namespace std;
    char c[10][10];
    int visit[10]={
        1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};
    int n,k;
    int numbers=0;
    void dfs(int x,int count){
        //行数（状态，递归这行为起点的路径），放的棋子数 ，状态的行数对应递归 
    	int flag = 0;
        if(x>=n)//当所搜索的行数大于棋盘时   直接返回
            return ; 
    	for(int i=0;i<n;i++){
        
    		flag = 0; 
    		if(c[x][i]=='#'){
        //if(c[x+1][i]=='#'){
        
    			for(int j=0;j<=count;j++){
        
    				if (i==visit[j]){
        
    					flag = 1;
    					break;
    				}
    			}
    			if(flag == 0){
        
                    visit[count]=i;
                    if(count+1==k){
        
                    	numbers = numbers+1;
    				}
    				dfs(x+1,count+1);
    				visit[count]=1000;
    			}
    			else{
        
    				continue;
    			}
    		}
    		else{
        
    			continue;
    		}
    	}
    	dfs(x+1,count);
    	return ;
    }
    
    int main(){
        
    	numbers = 0;
    	while(cin>>n>>k){
        
    		if(n==-1&&k==-1)
                break;
            for(int i=0;i<n;i++){
        
            	for(int j=0;j<n;j++){
        
            		cin>>c[i][j];
    			}
    		}
    		dfs(0,0);
            cout<<numbers<<endl;
            numbers = 0;
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

相关递归与递推+简单dfs

[821. 跳台阶][821.] ![在这里插入图片描述][344f33aad93f4c41bc5de20e2e42f2fe.png] 题解：这个题目只需要会递归就行算

比眉伴天荒/ 2024年03月26日 13:19/ 0 赞/ 113 阅读

相关 POJ 1321 棋盘问题（dfs）

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

以你之姓@/ 2024年02月17日 19:06/ 0 赞/ 92 阅读

相关 POJ 1321 棋盘问题 DFS

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

朴灿烈づ我的快乐病毒、/ 2024年01月22日 06:13/ 0 赞/ 85 阅读

相关 DFS回溯题：棋盘问题

DFS回溯题：棋盘问题问题： ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text

本是古典何须时尚/ 2023年10月06日 19:26/ 0 赞/ 23 阅读

相关递归与分治策略算法之棋盘覆盖问题

递归与分治策略算法之棋盘覆盖问题 1、先简单的来介绍一下分治策略的思想分治策略的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，分解出来的子问题与原问题相同

迈不过友情╰/ 2022年12月05日 04:58/ 0 赞/ 201 阅读

相关棋盘问题（dfs，递归）

按照行的顺序遍历，其中dfs(int x,int count)表示第x行已放置count个棋子状态下遍历放置的过程。需要注意的是for循环之后必须要加上一个dfs因为不能保障每

﹏ヽ暗。殇╰゛Y/ 2022年12月04日 09:15/ 0 赞/ 188 阅读

相关 poj 1321 棋盘问题 dfs暴力

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

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

相关 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 赞/ 220 阅读

相关棋盘分割（递归，动态规划）

193:棋盘分割总时间限制: 1000ms 内存限制: 65536kB 描述将一个８\８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩

今天药忘吃喽~/ 2022年06月10日 12:45/ 0 赞/ 223 阅读

相关棋盘问题（DFS）

Problem Description：在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请

喜欢ヅ旅行/ 2022年05月25日 06:27/ 0 赞/ 237 阅读