poj 1321 棋盘问题 DFS+回溯 回溯学习

最近刚刚学习回溯算法，标记一下，体会回溯的内涵

http://poj.org/problem?id=1321

棋盘问题

Time Limit: 1000MS		Memory Limit: 10000K

Description

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

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

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

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

2
1

/* Author : yan
 * Question : POJ 1321  棋盘问题
 * Data && Time : Monday, January 17 2011 01:20 PM
 * Compiler : gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
*/
//DFS+回溯  练习
#include<stdio.h>
#define true 1
#define false 0
#define bool _Bool
#define MAX 9
bool col_flag[MAX];
bool row_flag[MAX];
char map[MAX][MAX];
int size,k;
int sum,ans;
///参数sum 表示棋子个数，当sum==k时，停止
///参数col 表示位于棋盘中的列位置，当col==size时停止
int DFS(int sum,int col)
{
	if(sum>=k)
	{
		ans++;
		return;
	}
	if(col>size) return;
	int i;
	for(i=0;i<size;i++)//代表行号
	{
		if(map[i][col]=='#' && !row_flag[i] && !col_flag[col])//由于任意两个棋子不能在同一行或同一列
		{
			row_flag[i]=1,col_flag[col]=1;//标记该列该行已经有棋子
			DFS(sum+1,col+1);//处理棋子个数sum+1,处理下一列
			row_flag[i]=0,col_flag[col]=0;//回溯，重新将标记置位，用于下一步搜索
		}
	}
	DFS(sum,col+1);//如果该列没有合适的位置，继续搜索下一列
}
int main()
{
	freopen("input","r",stdin);

	int i,j;
	while(scanf("%d %d",&size,&k)&& size!=-1)
	{
		ans=sum=0;
		memset(row_flag,0,sizeof(row_flag));
		memset(col_flag,0,sizeof(col_flag));

		for(i=0;i<size;i++)
			for(j=0;j<size;j++) scanf(" %c",&map[i][j]);

		DFS(0,0);
		printf("%d/n",ans);
	}
	return 0;
}