百练+棋盘问题+dfs和回溯，模板化解题

点击打开链接

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<map>
#define LL long long
#define inf 0x3f3f3f3f
#define mod 1e9+7
using namespace std;
char Arr[8][8] = { '\0' };
int tot = 0, k = 0, n = 0, Map[8] = { 0 };
void dfs(int row, int p)
{
	int a = 0, b = 0;
	if (p == k) {///表示棋子数目都摆完。
		tot++;
		return;
	}
	if (row == n) return;///行数
	for (a = 0; a < n; a++){///列
        int ok=1;
		if (Arr[row][a] == '#'){
			for (b = 0; b < row; b++){///判断以上几行是否和当前行在一列。
				if (Map[b] == a){
                     ok=0;
                     break;
				}
			}
			if (ok){///表示满足不在同一列
				Map[row] = a;///递归回溯。
				dfs(row + 1, p + 1);
				Map[row] = -1;
			}
		}
	}
	dfs(row + 1, p);///这一层没有成功，进入下一层。
}
int main()
{
	int i = 0, j = 0;
	for (i = 0; i < 8; i++) Map[i] = -1;
	while (cin >>n>> k){
		if (n == -1 && k == -1) break;
		for (i = 0; i < n; i++){
			scanf("%s",Arr[i]);
		}
		dfs(0, 0);
		cout <<tot << endl;
		tot = 0;
	}
	return 0;
}