1
poj 1321 棋盘问题
::
解法1::dfs
题解
#include
#include
int n,k,count;
bool mp[10][10];
bool col[10];
void DFS(int x,int rest)
{
if(rest==0)
{
count++;
return;
}
if(x>n)
return;
for(int i=1;i<=n;i++) if(!col[i] && mp[x][i])
{
col[i]=true;
DFS(x+1,rest-1);
col[i]=false;
}
if(rest+x<=n)
DFS(x+1,rest);
}
int main()
{
// freopen("in.txt","r",stdin);
while(~scanf("%d%d",&n,&k) && n!=-1 && k!=-1)
{
memset(col,0,sizeof(col));
char str[20];
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
for(int k=1;k<=n;k++)
{
if(str[k]=='#')
mp[i][k]=true;
else
mp[i][k]=false;
}
}
count=0;
DFS(1,k);
printf("%d\n",count);
}
}
自解
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
char mp[50][50];
int v1[50];///hang
int v2[50];///lie
int n,k,ans=0;
void dfs(int x,int y,int k)
{
if(k==0) {ans++;return;}
for(int i=x+1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!v1[i]&&!v2[j]&&mp[i][j]=='#')
{
// printf("%d %d\n",i,j);
v1[i]=1;v2[j]=1;
dfs(i,j,k-1);
v1[i]=0;v2[j]=0;
}
}
}
return ;
}
int main()
{
while(~scanf("%d %d",&n,&k)){
if(n==-1||k==-1) break;
memset(v1,0,sizeof v1);
memset(v2,0,sizeof v2);
for(int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
}
ans=0;
for(int i=1;i<=n;i++)
{
if((n-i+1)<k) break;
for(int j=1;j<=n;j++)
{
if(mp[i][j]=='#'){
v1[i]=1;v2[j]=1;
dfs(i,j,k-1);
v1[i]=0;v2[j]=0;
}
}
}
printf("%d\n",ans);
}
}
解法2::状态压缩??没懂。。。5/13/019
状态转移分两种,当前行不加棋子,和加棋子。dp[i][j]中,i代表行数,j代表当前行棋子的状态。j的二进制中,1代表有旗子,0代表无棋子。
代码::
#include <cstdio>
#include <cstring>
int n,k,count;
bool mp[10][10];
int num[256];
int dp[9][256];
int main()
{
// freopen("in.txt","r",stdin);
for(int i=1;i<256;i++)
{
int tmp=i;
while(tmp)
{
if(tmp&1)
num[i]++;
tmp>>=1;
}
}
while(~scanf("%d%d",&n,&k) && n!=-1 && k!=-1)
{
char str[20];
for(int i=1;i<=n;i++)
{
scanf("%s",str+1);
for(int l=1;l<=n;l++)
{
if(str[l]=='#')
mp[i][l]=true;
else
mp[i][l]=false;
}
}
int status=1<<n;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<status;j++) if(num[j]<=k)
{
dp[i][j]+=dp[i-1][j];
for(int l=1;l<=n;l++) if(mp[i][l] && (j&(1<<(l-1)))==0)
{
dp[i][(j|(1<<(l-1)))]+=dp[i-1][j];
}
}
}
int ans=0;
for(int i=0;i<status;i++) if(num[i]==k)
ans+=dp[n][i];
printf("%d\n",ans);
}
}