碁盤問題DFS
1739 ワード
A-碁盤問題
Crawling in process...
Crawling failed
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の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
Sample Output
Crawling in process...
Crawling failed
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の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<stdio.h>
#include<string.h>
#include<math.h>
void dfs(int i,int k);
char e[10][10];
int col[11];
int n,k;
int count;
int main()
{
int i,j;
while(scanf("%d %d",&n,&k)==2)
{
if(n==-1&&k==-1) break;
memset(col,0,sizeof(col));
memset(e,0,sizeof(e));
count=0;
for(i=1;i<=n;i++)
{
scanf("%s",e[i]);
}
dfs(1,k);
printf("%d
",count);
}
return 0;
}
void dfs(int i,int k)
{
int j;
if(i>n+1) return;// , k==n, n , k 0
if(!k)
{
count++;
return ;
}
for(j=0;j<n;j++)
{
if(e[i][j]=='#'&&!col[j])
{
col[j]=1;
dfs(i+1,k-1);
col[j]=0;
}
}
dfs(i+1,k);
}