POJ-1321盤問題

1778 ワード

タイトル元リンク
碁盤問題
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 62010
 
Accepted: 29682
Description
1つの所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.並べ替え時に任意の2つの駒が碁盤の中の同一行または同一列に置かれないことを要求する場合は、所定の形状と大きさの碁盤に対してk個の駒を並べたすべての実行可能な並べ替えスキームCをプログラミングして解いてください.
Input
複数セットのテストデータを入力します. 
各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n <= 8 , k <= n 
-1-1の場合は入力が終了します. 
次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
Output
各セットのデータに対して、1行の出力が与えられ、配置されたシナリオ数Cが出力される(データ保証C<2^31).
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output
2
1

タイトル:2つの整数n,k,入力-1,-1を入力と入力が終了し、nはn*nの碁盤を表し、kは目標の駒の数を表し、碁盤の形状は不確定であるが、#は置くことができることを表す.k個の駒を全部で何種類の置き方があるかを聞く.
注意:条件を満たすかどうかを判断し、境界を越えたかどうかを判断する前後の順序.
#include
#include
using namespace std;
int n,k,cnt,t;
int vis[8];
char maze[8][8];
void dfs(int x)
{
	//     if,      ,               1;
	/*  :        ,                    ,
	     t         t   , x         ,     x     
	         ,  ,  t            ,     x    ;
	*/
	if(t==k)
	{
		cnt++;
		return ;
	}
	if(x>=n)
		return ;
	for(int j=0;j>n>>k&&n<=8&&k<=n&&n!=-1&&k!=-1)
	{
		cnt=0;//         ;
		t=0;//         ;
		for(int i=0;i>maze[i][j];
		memset(vis,0,sizeof(vis));//      :memset(vis,0,n*n);
		dfs(0);//                   ;
		cout<=n)
		return ;
	for(int j=0;j