A - 棋盘问题

桃扇骨 2022-08-07 09:50 185阅读 0赞

A - 棋盘问题  
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u  
Submit  
  
Status  
  
Practice  
  
POJ 1321  
Description  
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放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

#include <cstdio>
    #include <cstring>
    using namespace std;
    
    char ch[10][10];
    int n, k, ans;
    bool h[10];
    
    void dfs(int x, int y, int num)
    {
        if(num>k)  {    ans++; return;  }
        for(int i=x; i<n; i++){
            for(int j=0; j<n; j++){
                if( h[j]==false && ch[i][j]=='#'){
                    h[j]=true;
                    dfs(i+1, 0, num+1);
                    h[j]=false;
                }
            }
        }
    
    }
    
    int main()
    {
        while(scanf("%d%d", &n, &k) != -1){
            if(n==-1 || k==-1)  break;
            for(int i=0; i<n; i++)
                scanf("%s", ch[i]);
            memset(h, false, sizeof(h));
            ans = 0;
            dfs(0,0,1);
            printf("%d\n", ans);
        }
    
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 [kuangbin带你飞]专题一简单搜索 A棋盘问题

A - 棋盘问题题目链接：[https://vjudge.net/contest/65959\problem/A][https_vjudge.net_contest_6

深碍√TFBOYSˉ_/ 2023年08月17日 15:40/ 0 赞/ 97 阅读

相关棋盘覆盖问题

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

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

相关 1217：棋盘问题

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

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

相关棋盘问题

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

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

相关 A - 棋盘问题

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

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

相关棋盘问题

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

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

相关棋盘问题

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

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

相关棋盘问题（DFS）

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

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

相关 A - 棋盘问题

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

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

相关走格子/棋盘问题

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

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