単純検索(一)の碁盤問題
1820 ワード
323:ボードの問題
表示コミット統計質問合計時間制限:
1000ms
メモリの制限:
65536kB
説明
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の2つの駒を碁盤の中の同じ行または同じ列に置くことができないことを要求する場合は、所定の形状と大きさの碁盤に対して、k個の駒を置くすべての実行可能な配置スキームCをプログラミングして解いてください.
入力
複数セットのテストデータを入力します.
各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n <= 8 , k <= n
-1-1の場合は入力が終了します.
次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
しゅつりょく
各セットのデータに対して、1行の出力が与えられ、配置されたシナリオ数Cが出力される(データ保証C<2^31).
サンプル入力
表示コミット統計質問合計時間制限:
1000ms
メモリの制限:
65536kB
説明
所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.任意の2つの駒を碁盤の中の同じ行または同じ列に置くことができないことを要求する場合は、所定の形状と大きさの碁盤に対して、k個の駒を置くすべての実行可能な配置スキームCをプログラミングして解いてください.
入力
複数セットのテストデータを入力します.
各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n <= 8 , k <= n
-1-1の場合は入力が終了します.
次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
しゅつりょく
各セットのデータに対して、1行の出力が与えられ、配置されたシナリオ数Cが出力される(データ保証C<2^31).
サンプル入力
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
： -- 。 ， ， 。 ， 。 。#include
#define MAX 10
using namespace std;
char maps[MAX][MAX];
int n,k,num;
int vis[MAX];
long long cnt;
void dfs(int i){
if(num==k){
cnt++;
return ;
}
if(i>=n){
return ;
}
dfs(i+1);// /* ， */
for(int j=0; j if(maps[i][j]=='#'&&vis[j]==0){
vis[j]=1;
num++;
dfs(i+1);
num--;
vis[j]=0;
}
}
}
int main()
{
while(cin>>n>>k){
if(n==-1 && k==-1){
return 0;
}
for(int i=0; i for(int j=0; j cin>>maps[i][j];
}
}
memset(vis,0,sizeof(vis));
cnt=0;
num=0;
dfs(0);
cout<
}
return 0;
}