POJ 1321碁盤問題(DFS
1496 ワード
万博に行って棺を開けて帰ってきた
ここ数日dfsを見るのに長い時間がかかった(実は心を込めて見ていないので、いつも気を散らしている.
くだらないことは言わない:前の第1題:
POJ 1321ディスクの問題:
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の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
AC CODE:
自分の理解力が本当に悪いことに気づいて、白書とたくさんのdfs紹介を読んで、本当にこの問題をDFSとつなぐことができなくて、ああ、、、、やはりネット上でいくつかの問題解を見て、瞑想を加えてやっとだんだん理解して、この問題はもっとマークをつけなければならなくて、同じ行の同じ列が繰り返して置くことができないためです...
こんな料理の私は...明日また別の問題をやりましょう
毎回ACが感動する
がんばって!前途は明らかだ君とぼくが共に進む
ここ数日dfsを見るのに長い時間がかかった(実は心を込めて見ていないので、いつも気を散らしている.
くだらないことは言わない:前の第1題:
POJ 1321ディスクの問題:
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の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
AC CODE:
#include
#include
#include
using namespace std;
int n,k;
int king;
char a[11][11];
bool wyh[11];
void dfs(int num,int cnt)
{
if(num==k){
king++;
return ;
}
if(cnt>n)
{
return ;
}
for(int i=0;i>a[i][j];
}
}
dfs(0,0);
printf("%d
",king);
}
return 0;
}
/*2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1*/
自分の理解力が本当に悪いことに気づいて、白書とたくさんのdfs紹介を読んで、本当にこの問題をDFSとつなぐことができなくて、ああ、、、、やはりネット上でいくつかの問題解を見て、瞑想を加えてやっとだんだん理解して、この問題はもっとマークをつけなければならなくて、同じ行の同じ列が繰り返して置くことができないためです...
こんな料理の私は...明日また別の問題をやりましょう
毎回ACが感動する
がんばって!前途は明らかだ君とぼくが共に進む