棋盘问题（dfs，递归）

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

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

相关阅读

相关递归与递推+简单dfs

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

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

相关 POJ 1321 棋盘问题 DFS

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

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

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

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

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

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

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

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

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

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

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

相关 poj 1321 棋盘问题 dfs暴力

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

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

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

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

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

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

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

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

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

相关棋盘问题（DFS）

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

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