这个题要是乍一看很难会想深搜,确实如此,可如果知道了深搜的方法,这个题就简
了不少,至于用深搜的时候要考虑当k==n和k<n时这咱种情况,当K==n时,当然很好想
到深搜搜下很容易找到所有方法,,但是当k<n时就得考虑后面的情况,
所以后面加了个dfs(row+1,num)主要是这种情况的考虑。#include <stdio.h>
#include <string.h>
#include <iostream>
#include <cstring>
using namespace std;int used[9][9],n,number,k,colvis[9];//colvis用于放置棋子的列标记
char c;void dfs (int row,int num)
{
if (num==k)//当一种方式搜完后,方式加 1;
{
number++;
return;
}
if (row > n)return ;//当行数超过时,深搜结束。
for (int j=1; j<=n; j++)
{
if (used[row][j] && !colvis[j])
{
colvis[j] = 1;
dfs(row+1,num+1);
colvis[j] = 0;//回溯后,说明摆好棋子的状态已记录,当前的列标记还原
}
}
dfs(row+1,num);
return;
} int main()
{ while (scanf("%d%d",&n,&k)!=EOF )
{
if (n==-1 && k==-1)break;
number = 0;
memset(colvis,0,sizeof(colvis));
memset(used,0,sizeof(used));
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
{
cin >> c;
if (c=='#')
used[i][j] = 1;
}
dfs(1,0);
printf("%d\n",number);
}
return 0;
}
中文题
dfs 搜完把同行同列全置为不可用就行了