搜索专题

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);
    }
}