poj_1321_碁盤問題

2219 ワード

碁盤問題
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 59097
 
Accepted: 28382
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

テーマ:
n,kを入力し,n次行列を入力する.n*nの碁盤の格子の上でk個の駒(駒の間は区別がありません)を入れて、同業者の異なる列にいないで、しかも駒は#の位置でしか置くことができなくて、
すべてのシナリオ数を求める.
分析:テーマは同業者の異なる列を要求しないで、前の検索図の方法に従って位置ごとに検索する必要はなくて、比較的に時間がかかっても検索しにくいかもしれません.私たちは1行に1つを見つけて、次の行に変えて探し続けるだけでいいです.すべてを探してから別の案を遡って探して、すべての案の数を見つけます.
コード:
#include 
#include 
#include 
#include 
using namespace std;
int n,k;
int num ,step;
char str[10][10];
int book[10];

void dfs(int x)
{
    if(step == k)      //     k   ,    1 
    {
        num++;
        return ;
    }
    if(x >= n)  //      
        return ;
    for(int j=0;j

Javaコード:
import java.util.*;
public class Main {
	static int n,k;
	static int book[] = new int[10];
	static char[][] s = new char[10][10];
	static int num,step;
	
	public static void dfs(int x) {
		if(step == k)
		{
			num++;
			return ;
		}
		if(x >= n)
			return ;
		for(int j=0;j