poj 1321搜索的问题（DFS，回溯）

题意：在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n

当为-1 -1时表示输入结束。

随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

 

思路：这题只需要深搜，每次从上一个放棋子地方的下一行开始寻找可以放棋子的地方，当发现该点时，记录行数，并更新棋盘，将于此点同行同列的都更新为'.'，如果找不到，则返回，当把所有棋子都放上去的时候，则找到一个接，计数+1，就这样进行搜索，可以保证AC。由于题意中明确的提出C<2^31，这样int类型就能满足，设计时就不用考虑这个数据类型了！

代码如下：

#include<iostream>
using namespace std;
const int Max = 10;



bool board[Max][Max], row[Max], col[Max];  // row[i],col[j]分别记录第i行，第j列被访问了没有。
int len, num, ans;



void dfs(int depth, int start_line)
{
    if(depth == num)
	{
        ans ++;
        return;
    }
    for(int i = start_line + 1; i <= len; i ++)
        for(int j = 1; j <= len; j ++)
            if(board[i][j] == true && row[i] == false && col[j] == false)
			{
                row[i] = true;  
				col[j] = true;
                dfs(depth + 1, i);
                row[i] = false;  
				col[j] = false;
            }
}



int main()
{
    int i, j;
    char c;
	
    while(1)
	{
        cin >> len >> num;

        if(len == -1 && num == -1) 
			break;
        memset(board, false, sizeof(board));
        for(i = 1; i <= len; i ++)
            for(j = 1; j <= len; j ++)
			{
                cin >> c;
                if(c == '#')
                    board[i][j] = true;
            }
			
			ans = 0;
			memset(row, false, sizeof(row));
			memset(col, false, sizeof(col));
			int start_line = len - num + 1; // 第一颗棋子的位置可能在 1 ~ start_line 行之间。
			for(i = 1; i <= start_line; i ++)
				for(j = 1; j <= len; j ++)
					if(board[i][j] == true)
					{
						row[i] = true;  
						col[j] = true;
						dfs(1, i);
						row[i] = false;  
						col[j] = false;
					}
					cout << ans << endl;
	}
	return 0;
}

 关于代码中的回溯问题，现在说实在的不能理解啊~！真的想了好久，还是不懂！要向别人去请教一下才能懂！！