A8004.棋盘问题:题解

食用说明:这是一道DFS题目,如果先前没有接触过这一类的题目,建议可以先看

Macw07的深度优先搜索 DFS:https://www.acgo.cn/discuss/study/19056

正文开始:

题目大意:
要求输出在n*n的棋盘中摆放k个不在棋盘同一行或同一列的棋子的不同方案数

*用字符 #表示可以放棋子的位置,用字符.表示不可以放棋子的位置

题目思路:
利用DFS尝试在每一行放置棋子,并在成功放置k个棋子时,增加answer(方案数)

注意:使用回溯法

*回溯法:适用于这种需要枚举所有可能性的问题。通过递归地尝试每个可能的位置，并在不符合条件时回退。(来源:AC助手)

关键点思考:如何判断某个位置可以放置棋子?

1.确保这个位置所在的行,列都没有其他棋子

如何确保每个棋子在不同行和不同列?
这里,可以使用两个一维数组来记录放置过棋子的行和列:

bool h[10];
bool l[10];

2.确保此位置本身可以放棋子(确保其为#字符)

解题代码:

#include<bits/stdc++.h>
using namespace std;
int n,k;
char a[10][10];
bool h[10];
bool l[10];
int answer=0;
//answer:方案数
void dfs(int x,int qi){
    //如果放置数满足条件,则让方案数++;
	if(x==k){
		answer++;
        return;//返回
	}
	for(int i=qi;i<=n;i++){
        //注意:这里的i并不是从1开始的,而是从上一轮的i开始的
        //如果从1开始,因为有回溯,会算重(计算重复数据)
		if(!h[i]){//如果第i行没有标记(没有放置的棋子),开始枚举列数(查看是否有符合条件,可以放置棋子的位置)
			for(int j=1;j<=n;j++){
                //这里的j是从1开始的,而不是上一轮的j,因为在上一轮被筛除的列数,在这一轮可能可以用上)
                //比如在上一轮中,第i行第j列可能是'.'(不能放置棋子),然后发现第i行第j+1列可以
                //如果在这一轮直接从j+1开始,那可能会错过原本可行的第i+1行第j列,而直接从第i+1行第j+1列开始枚举
				if(!l[j]){
                    //如果第j行没有放置的棋子,开始查看第i行第j列是否可以放置棋子
					if(a[i][j]=='#'){
                       //如果可以放置,标记h[i]和l[j](第i行,第j列)
						h[i]=1;
					    l[j]=1;
					    dfs(x+1,i);
                        //回溯
					    h[i]=0;
					    l[j]=0;    
					}
				}
			}
		}
	}
}
int main(){
	while(1){
		cin>>n>>k;
        //每次都需要重置数组和answer,不然会影响答案
        answer=0;
        memset(h,0,sizeof(h));
        //memset的使用方法:memset(数组名,0/-1(希望填充的数据),sizeof(数组名))
        //作用:可以将数组整个赋值为0/-1
        memset(l,0,sizeof(l));
		if(n==-1&&k==-1){
			return 0;
		}else{
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					cin>>a[i][j];
				}
			}
			dfs(0,1);
			cout<<answer<<endl;
		}
	}
}