POJ 1321 经典棋盘问题 的搜索和状态压缩解法

本文主要是介绍POJ 1321 经典棋盘问题 的搜索和状态压缩解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这就是 n 皇后问题，不过简单了点，对于对角线不做限制

搜索，因为只有 8！个状态，直接数就可以了

状态压缩dp，每一行用一排1010代表上面有没有放过旗子，1是放过，0是没有，这一个行的状态可以是完全来自以前或者在这一行合法的地方放一个棋子。

每行有 2^n 种状态，共 n 行，每次转移要 n，总的就是 2^n*n*n;

两种代码 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>using namespace std;
#define MAX 1000009 
#define INF 0x3f3f3f3f
#define MS(x) memset(x,0,sizeof(x))
#define ll long long
#define P pair<int,int>
#define fst first
#define sec secondint ans;
char b[20][20];
int n;
void dfs(int r,int state,int k)
{if(!k){ans++;return ;}if(r>=n)return ;dfs(r+1,state,k);for(int i=0;i<n;i++){if(((1<<i)&state)==0&&b[r][i]=='#'){dfs(r+1,(1<<i)|state,k-1);}}
}int main()
{int k;while(scanf("%d%d",&n,&k)!=EOF&&n!=-1){ans=0;for(int i=0;i<n;i++)scanf("%s",b[i]);dfs(0,0,k);cout<<ans<<endl;}return 0;
}

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>using namespace std;
#define MAX 1000009 
#define INF 0x3f3f3f3f
#define MS(x) memset(x,0,sizeof(x))
#define ll long long
#define P pair<int,int>
#define fst first
#define sec secondint dp[10][1000];
char b[11][11];
int cnt[2000];
int n,k;
int check(int n)
{int ans=0;while(n){if(n%2)ans++;n/=2;}return ans;
}
int main()
{for(int i=0;i<1000;i++)cnt[i]=check(i);while(scanf("%d%d",&n,&k)&&n!=-1){MS(dp);for(int i=1;i<=n;i++)scanf("%s",b[i]+1);dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<(1<<n);j++){if(cnt[j]<=k){dp[i][j]+=dp[i-1][j];for(int p=1;p<=n;p++){if( ((1<<p-1)&j) && b[i][p]=='#'){dp[i][j]+=dp[i-1][(~(1<<p-1))&j];}}}	}	}int ans=0;for(int i=0;i<(1<<n);i++)if(cnt[i]==k)ans+=dp[n][i];cout<<ans<<endl;}return 0;
}

这篇关于POJ 1321 经典棋盘问题 的搜索和状态压缩解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---