棋盘问题——深度优先搜索
题目描述：
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
详情请看poj1321: https://vjudge.net/problem/POJ-1321#author=0
解题思路：
按行进行深搜，总的方案数 = 选取该行中某位置的方案数 + 不选取该行位置的方案数，直至棋子数位0或达到最后一行
代码如下：
#include<stdio.h>
#include<iostream>
using namespace std;
int ans = ;
char map[][];
int result[];
int n, k; /********************检查是否冲突*****************/
int Check(int row,int col)
{
int flag = ;
if (row == )
return flag;
for (int i = ; i < row; i++)
{
if (result[i] == col)
flag = ;
}
return flag;
} /*************按行搜索，从第row行开始，放k个的方法数*******/
void Dfs(int row,int k)
{
if (row == n || k == ) //要开考虑到row == n 且 k == 0的情况
{
if (k == )
ans++;
return;
}
for (int col = ; col < n; col++)
{
if (map[row][col] == '#' && Check(row, col))
{
result[row] = col;
Dfs(row + , k-);
}
}
Dfs(row + , k);
return;
}
int main()
{
memset(result, -, sizeof(result));
memset(map, -, sizeof(map));
while (cin>>n>>k && (n != - && k != -))
{
for (int i = ; i < n; i++)
{
for (int j = ; j < n; j++)
{
//scanf("%c", &map[i][j]); //我也不知道为什么不能用scanf,希望大佬看到了能解释一下
cin >> map[i][j];
}
}
Dfs(,k);
cout << ans<<endl;
ans = ; //记得归零
}
return ;
}
我也是刚接触的小白，什么不懂的，希望大家能在下面一起讨论