棋盘问题-题解

题目：普及难度 DFS算法 洛谷

分析

这个题目乍眼一看类似小学奥数排列组合

但是这个题目不能单纯去C(n,k)或者乘法原理求解

因为 题目要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列

我们可以进行枚举每一种可能的方案来求解，也就是暴力枚举

但是每一次落子都会影响后面的落子情况，如果使用For循环的话肯定是不行的

像这样根据上一步会推导影响下一步的问题，一般可以使用DFS深搜

毕竟深搜也算是暴力枚举的一种awa

实现:DFS

既然题目给的是棋盘，那么创建二维数组G存储棋盘数据

如题目要求每一种可能方案，因此我们将每个可以放的位置都进行深搜

for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		if(G[i][j]=='#'){ 可以摆放
			dfs(i,j); 进行深搜
		}
	}
} 

同时DFS内我们设cnt存储当前已落下棋子数

进入DFS内对棋盘进行标记 (确保下一个落子地方满足要求)

然后再如一开始DFS后面的可能落子点

但是此处如何标记呢？？？

可以想象一下存储的二维棋盘
如：

. . . #
. . # .
. # . .
# . . .

我们可以在再这个棋盘的第一行和第一列前再加一列，用以存储标记

如：

0 0 0 0 0
0 . . . #
0 . . # .
0 . # . .
0 # . . .

当这个棋子落下时将它该行的前标记改为A，将它该列的前标记改为A

如前面案例，落子于(1,5)就将图改为

0 0 0 0 A
A . . . #
0 . . # .
0 . # . .
0 # . . .

这样当DFS时如果行列的前标记为A时，跳过该落子点

不要忘记回溯

代码

#include <bits/stdc++.h>
using namespace std;
int n,k,cnt,sum;
char G[15][15];
void dfs(int x,int y){
	cnt++;
	G[x][0]=G[0][y]='A';//标记
	if(cnt==k){sum++;return ;}
	for(int i=x;i<=n;i++){
		for(int j=1;j<=n;j++){ 
			if(G[i][j]=='#'&&G[i][0]!='A'&&G[0][j]!='A'){
				dfs(i,j);
				//回溯
				cnt--;G[i][0]=G[0][j]='0';
			}
		}
	}
}
int main(){
	memset(G,'0',sizeof(G));
	cin>>n>>k;
	while(n!=-1&&k!=-1){
		for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>G[i][j];}}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(G[i][j]=='#'){
					dfs(i,j);
					//回溯
					cnt--;G[i][0]=G[0][j]='0';
					
				}
			}
		} 
		cout<<sum<<endl;
		cnt=sum=0;
		cin>>n>>k;
	}
	return 0;
}