POJ-1321-碁盤問題【DFS】
碁盤問題
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
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
タイトルリンク:POJ-1321
な を えて、‘#’のところに を くことができます. でk の があって、これらの は で じ に ぶことができなくて、いくつかの を きます.
テーマ : に ている.
コードは のとおりです.//
// main.cpp
//
//
// Created by pro on 16/3/21.
// Copyright (c) 2016 pro. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#include<iomanip>
using namespace std;
string s[10];
int line[10]; // i
int ans = 0;
int n,k;
int cnt = 0;
void dfs(int row)
{
if (cnt == k)
{
ans ++;
return;
}
if (row >= n)
{
return;
}
for (int i = 0; i < n; i++)
{
if (s[row][i] == '#') //
{
int ok = 1;
for (int j = 0; j < cnt; j++) // < cnt
{
if (line[j] == i)
{
ok = 0;
break;
}
}
if (ok)
{
line[cnt++] = i; // cnt i
dfs(row + 1);
cnt--;
}
}
}
dfs(row + 1); //
}
int main()
{
while(cin >> n >> k)
{
memset(line,-1,sizeof(line));
ans = 0,cnt = 0;
if (n == -1 && k == -1) break;
for (int i = 0; i < n; i++) cin >> s[i];
dfs(0);
cout << ans << endl;
}
return 0;
}