编程介的小学生 2019-10-02 10:13 采纳率: 20.5%
浏览 590

解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案

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

  • 写回答

1条回答 默认 最新

  • 关注
    #include<iostream>
    #include <algorithm>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    int visit[20];
    char mp[20][20];
    int ans;
    int k;
    int n; 
    int DFS(int x,int y)
    {
        if(y==k)
        {
            ans++;
            return 0;
        }
        for(int i=x;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(!visit[j]&&mp[i][j]=='#')
                {
                    visit[j]=true;
                    DFS(i+1,y+1);
                    visit[j]=false;
                }
            }
        }
        return 0;
    }
    int main()
    {
        while(cin>>n>>k)
        {
            if(n==-1&&k==-1)
                break;
            memset(visit,false,sizeof(visit));
            memset(mp,false,sizeof(mp));
            for(int i=0;i<n;i++)
                cin>>mp[i];
            ans=0;
            DFS(0,0);
            cout<<ans<<endl;
        }
        return 0;
    }
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题