题目链接
http://poj.org/problem?id=1321
题意
给定一块棋盘(棋盘可能是不规则的),有k个相同棋子,将k个棋子摆放在棋盘上,使得任意两个棋子不同行,不同列,求有多少种不同的摆法。
思路
此题和八皇后问题很像,需要注意摆放完毕后要恢复现场,便于下一次摆放。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int N = ;
char board[N][N];
int visit[N]; //visit[j]=1表示第j列有棋子, 0表示无棋子
int n, k;
int cnt; //摆放方案数 void dfs(int k, int r)
{
if(k==)
{
cnt++;
return;
} for(int i=r; i<N; i++)
{
for(int j=; j<N; j++)
{
if(board[i][j]=='#'&& !visit[j])
{
visit[j] = ;
dfs(k-, i+); //从下一行开始搜索
visit[j] = ; //恢复现场,便于回溯
}
}
}
} int main()
{
//freopen("poj1321.txt", "r", stdin);
while(cin>>n>>k)
{
if(n==-)
return ;
for(int i=; i<n; i++)
cin>>board[i]; memset(visit, , sizeof(visit));
cnt = ;
dfs(k, );
cout<<cnt<<endl;
}
return ;
}