棋盘问题

问题描述

解决思路

深度优先搜索，用一个数组vis记录已经放好棋子的状态,当放好之后再，撤销。
详细代码如下；

#include<stdio.h>
#include<string.h>
int n,k,vis[15],ans;
//全局变量k，n
//k需要摆放的棋子的总个数
//全局变量ans,解决方案个数
char mat[15][15];
//储存矩阵使用
void dfs(int cur,int num)
{
    //cur记录当前行位置
    //num记录已经放置的棋子数
    if(num==k)
        //所有的棋子已经摆好
    {
        ans++;

    }
    //开始回溯
    for(int i=cur;i<n;i++)
    //从当前行数开始找直到找到可以放置棋子的那一行
        for(int j=0;j<n;j++)
            //从第current行的第一列开始
            if(mat[i][j]=='#' && !vis[j])
            //能放棋子的条件
            {
                vis[j]=1;
                //在第j列试探性的放棋子
                dfs(i+1,num+1);
                //再已经放好棋子的下一行开始放置棋子
                //同时已经放好的棋子数加一
                //放完之后再撤销到这一步
                vis[j]=0;
                //撤销在第j列放置的棋子
            }
}
int main()
{
    while(~scanf("%d %d%*c",&n,&k) && n!=-1 && k!=-1)
    {
        memset(vis,0,sizeof(vis));
        //初始化visit
        int i;
        for(i=0;i<n;i++)
            gets(mat[i]);
            //赋值输入
        ans=0;
        //满足条件的方案
        dfs(0,0);
        //cur当前行位置，
        //深度优先搜索
        printf("%d\n",ans);
        //输出满足条件的方案
    }
    return 0;
}
//dfs理解
//二叉树的先序遍历本质上就是dfs
//*******棋盘问题**//