一本通——1217棋盘问题

1001-高同学

发表文章数:265

热门标签

首页 » LeetCode » 正文

 

1217:棋盘问题

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 6763     通过数: 3157

【题目描述】

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

【输入】

输入含有多组测试数据。

每组数据的第一行是两个正整数n,kn,k ,用一个空格隔开,表示了将在一个n×nn×n 的矩阵内描述棋盘,以及摆放棋子的数目。 (n≤8,k≤n)(n≤8,k≤n)

当为−1−1−1−1 时表示输入结束。

随后的nn 行描述了棋盘的形状:每行有nn 个字符,其中 ## 表示棋盘区域,.. 表示空白区域(数据保证不出现多余的空白行或者空白列)。

【输出】

对于每一组数据,给出一行输出,输出摆放的方案数目CC (数据保证C<231C<231

#include <bits/stdc++.h>
using namespace std;
#define MAXN 35

int dx[4]= {1,0,-1,0};
int dy[4]= {0,-1,0,1};
char mp[MAXN][MAXN];
int qizi[MAXN][2];

int col[MAXN];
int n,k,cnt;

void dfs(int step)
{
    for(int i=qizi[step-1][0]+1; i<=n-k+step; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(mp[i][j]=='#'&&col[j]==0)
            {
                col[j]=1;
                qizi[step][0]=i;
                if(step==k)
                    cnt++;
                else
                    dfs(step+1);
                col[j]=0;
                qizi[step][0]=0;
            }
        }
    }
    return ;
}

int main()
{
    int i,j;
    cin>>n>>k;
    while(n!=-1&&k!=-1)
    {
        memset(qizi,0,sizeof(qizi));

        memset(col,0,sizeof(col));
        cnt=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                cin>>mp[i][j];
            }
        }
        dfs(1);
        cout<<cnt<<endl;
        cin>>n>>k;
    }
    return 0;
}

 

标签:

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《一本通——1217棋盘问题》 发布于2020-02-13

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录