棋盘问题

柔光的暖阳◎ 2022-06-11 07:29 200阅读 0赞

棋盘问题

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

Input

输入含有多组测试数据。  
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n\*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n  
当为-1 -1时表示输入结束。  
随后的n行描述了棋盘的形状：每行有n个字符，其中 \# 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

Sample Input

2 1
    #.
    .#
    4 4
    ...#
    ..#.
    .#..
    #...
    -1 -1

Sample Output

2
    1

题目解析：

这是一个简单的DFS题

代码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int maxn=100;
    char s[maxn][maxn];
    int vis[maxn];
    int n,k,ans;
    int DFS(int row,int cnt)
    {
        if(cnt>=k)
        {
            ans++;
            return 0;
        }
        for(int i=row;i<n;i++)
            for(int j=0;j<n;j++)
            if(!vis[j]&&s[i][j]=='#')
        {
            vis[j]=1;
            DFS(i+1,cnt+1);
            vis[j]=0;
        }
        return 0;
    
    }
    int main()
    {
       //freopen("in.txt","r",stdin);
        while(cin>>n>>k&&n+k!=-2)
        {
            ans=0;
            memset(s,0,sizeof(s));
            memset(vis,0,sizeof(vis));
            for(int i=0;i<n;i++)
                cin>>s[i];
            DFS(0,0);
            cout<<ans<<endl;
        }
    
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关棋盘覆盖问题

棋盘覆盖问题在一个2k✖2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，并且这个棋盘就称为特殊棋盘。显然，这个特殊方格在棋盘中出现的位置由4k中

曾经终败给现在/ 2023年06月11日 08:23/ 0 赞/ 9 阅读

相关棋盘覆盖问题题解

文章目录问题代码 -------------------- 问题在一个2k × 2k个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方

一时失言乱红尘/ 2022年12月28日 14:15/ 0 赞/ 315 阅读

相关 1217：棋盘问题

1217：棋盘问题经典搜索问题时间限制: 1000 ms 内存限制: 65536 KB 提交数: 8752 通过数: 4145 【题目描述】在一个给定

约定不等于承诺〃/ 2022年12月13日 12:42/ 0 赞/ 157 阅读

相关棋盘问题

棋盘问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述在一个给定形状的棋盘（形状

Bertha 。/ 2022年08月18日 02:22/ 0 赞/ 161 阅读

相关 A - 棋盘问题

A - 棋盘问题 Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit

桃扇骨/ 2022年08月07日 09:50/ 0 赞/ 170 阅读

相关棋盘问题

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

素颜马尾好姑娘i/ 2022年07月13日 01:29/ 0 赞/ 185 阅读

相关棋盘问题

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

柔光的暖阳◎/ 2022年06月11日 07:29/ 0 赞/ 201 阅读

相关棋盘问题（DFS）

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

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

相关 A - 棋盘问题

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

雨点打透心脏的1/2处/ 2022年03月20日 07:58/ 0 赞/ 180 阅读

相关走格子/棋盘问题

1，给定一个n\n的格子或棋盘，问从左下角走到右上角的走法总数（每次只能向右或向上移动一个方格边长的距离）解答：我们可以把棋盘的左下角看做二维坐标的原点(0,0)，把棋盘的

朱雀/ 2021年11月19日 14:46/ 0 赞/ 311 阅读