棋盘问题（dfs，递归）

﹏ヽ暗。殇╰゛Y 2022-12-04 09:15 151阅读 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 条评论，151人围观）

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

相关阅读

相关 poj 3984 迷宫问题 —— 典型搜索--DFS递归

四个方向，每次选择一个方向走，不通时走下一个方向，如果四个方向都不能走时，则退一格。依题意，可用DFS递归实现。 include<stdio.h> inclu

系统管理员/ 2023年01月16日 06:56/ 0 赞/ 123 阅读

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

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

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

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

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

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

相关递归问题

关于递归求二进制的一点小问题看下面的代码，虽然只是多了一个等号，但是结果却不一样，要深刻理解。 void to(int num) { print

阳光穿透心脏的1/2处/ 2022年09月24日 09:23/ 0 赞/ 139 阅读

相关 poj 1321 棋盘问题 dfs暴力

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

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

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

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

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

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

相关数据结构：整数划分问题 + DFS递归解决

问题是什么整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式： n=m1+m2

Love The Way You Lie/ 2022年05月31日 12:30/ 0 赞/ 194 阅读

相关棋盘问题（DFS）

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

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

相关递归问题

题目如图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

叁歲伎倆/ 2022年05月03日 08:00/ 0 赞/ 183 阅读