poj 1321 排兵布阵问题 dfs算法

题意：有不规则地图，在上面放n个相同的棋子，要求摆放的时候不同行不同列。问：有多少种摆法？

思路：dfs+回溯

1. 用一个book[]数组来表示当前列是否有放棋子
2. 一行一行的遍历，对一行来说遍历它的列，如果满足book[i] == 0 && map[cur][i] == '#'  则可以摆放，然后继续遍历下一行

代码上需要注意的地方：

for (int i = 0; i<n; i++)
        if (book[i] == 0 && map[cur][i] == '#')
        {
            book[i] = 1;
            m++;
            dfs(cur + 1);
            book[i] = 0;
            m--;
        }

其中有个回溯的操作，为什么？

     因为如果当前没有执行dfs(cur+1)这个语句的话，说明i这个位置不能摆放棋子，或者说摆放棋子不妥。所以需要往回标记

解决问题的代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
char map[9][9];
int n, k;
int total, m;
int book[9];
void dfs(int cur)
{
    if (k == m)
    {
        total++;
        return;
    }
    if (cur >= n)
        return;
    for (int i = 0; i<n; i++)
        if (book[i] == 0 && map[cur][i] == '#')
        {
            book[i] = 1;
            m++;
            dfs(cur + 1);
            book[i] = 0;
            m--;
        }
    dfs(cur + 1);
}
int main()
{
    while (scanf("%d%d", &n, &k) != EOF)
    {
        if (n == -1 && k == -1)
            break;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
        dfs(0);
        printf("%d
", total);
        m = total = 0;
    }
    return 0;
}