【DFS】POJ 1321

时间:2024-10-11 14:05:32

POJ 1321 棋盘问题

题意:中文题不解释。

思路:经典DP,比较取巧的想法是一行行(按照题目意思一行最多只能放一个)来看,标记一列列。注意考虑到有些行可能不放的情况。

/**
Sample Input 2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output 2
1
**/ #include<cstdio>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 15;
char maps[maxn][maxn];
int vis[maxn];
int ans;
int n,k;
void dfs(int c,int cnt){
if(cnt == k){
ans++;
return ;
}
if(c >= n)
return ;
for(int i=0;i<n;i++){
if(!vis[i]&&maps[c][i]=='#'){ //该列没有访问过,而且可以放棋子
vis[i] = 1;
dfs(c+1,cnt+1);
vis[i] = 0;
}
}
dfs(c+1,cnt); //这一行也可以不放
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
ans = 0;
memset(vis,0,sizeof(vis));
if(n==-1&&k==-1)
break;
for(int i=0;i<n;i++){
scanf("%s",maps[i]);
}
dfs(0,0);
printf("%d\n",ans);
}
return 0;
}