POJ 1312盤問題【簡単検索】【dfs】

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

Source
蔡錯@pku
 
非常に典型的な深さ検索問題で、遡及が終わるとタグ配列を0にリセットします.検索ローの数を階層的に繰り返すたびに、カラムがマークされているかどうかを確認します(マークされている場合は、ローにすでに駒が配置されていることを意味します).

#include
#include
#include
#include
#include
using namespace std;
#define LL long long
#define M(a,b) memset(a,b,sizeof(a))
const int MAXN = 15;
const int INF = 0x3f3f3f3f;
int n,k;
int MAP[MAXN][MAXN];
int vis[MAXN];
int sum;
void dfs(int x,int num)///x   ，num         。
{
    if(num==k)///  k          
    {
        sum++;
        return;
    }
    for(int i=x; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(MAP[i][j]==1&&vis[j]==0)///        ，              。
            {
                vis[j]=1;///         
                dfs(i+1,num+1);///     ，      +1
                vis[j] = 0;///          ，       0
            }
        }
    }

    return ;
}
int main()
{
    while(scanf("%d %d",&n,&k)&&n!=-1&&k!=-1)
    {
        M(MAP,0);
        M(vis,0);
        sum=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                char temp;
                cin>>temp;
                if(temp=='#') MAP[i][j]=1;
            }
        }
        dfs(1,0);
        printf("%d
",sum);

    }
    return 0;
}