poj1321
1407 ワード
タイトル:碁盤問題
タイトルリンク:http://poj.org/problem?id=1321
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
考え方:dfs簡単な問題
コードは次のとおりです.
タイトルリンク:http://poj.org/problem?id=1321
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
考え方:dfs簡単な問題
コードは次のとおりです.
#include
#include
#include
#include
#include
using namespace std;
char a[9][9];
int C[9];
int sum=0;
int n,k;
void dfs(int cnt,int t)
{
if(t==k)
{
sum++;
}
else
{
for(int j=1;j<=n;j++) //
{
if(a[cnt][j]=='#'&&C[j]==0)
{
C[j]=1;
dfs(cnt+1,t+1);
C[j]=0;
}
}
if(cnt