【POJ 1321】碁盤問題(dfs)
9064 ワード
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
構想
八数コードに似ています.詳細はコードを参照してください.
コード#コード#
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
構想
八数コードに似ています.詳細はコードを参照してください.
コード#コード#
#include
#include
using namespace std;
char mat[10][10]; //
int vis[10]; //
int cnt=0; //
int n,k;
// x , y
void dfs(int x, int y)
{
//
for(int i=1;i<=n;i++)
{
//
if(mat[x][i]=='#' && !vis[i])
{
if(y==1){
cnt++;
return ;
}
else
{
vis[i]=1;//
// , y-1
for(int j=x+1;j<=n-y+2;j++)
dfs(j,y-1);
vis[i]=0;//
}
}
}
return;
}
int main()
{
while(cin>>n>>k &&n>0)
{
cnt=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mat[i][j];
for(int i=1;i<=n-k+1;i++)
dfs(i,k);
cout<<cnt<<endl;
}
return 0;
}