首页 > POJ解题报告 > POJ 1321 棋盘问题[DFS]

POJ 1321 棋盘问题[DFS]

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

深搜,某一行放不放子的问题,大概是这样。中间判断一下某一列可不可以放子就好了。DFS返回条件是没有子可放了或者行数超出限制了。题目的数据量也不算大,直接用朴素的DFS就可以解决了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
bool flag[10];
bool dic[10][10];
int res, n;
 
void DFS(int r, int k)
{
	if (k == 0)
	{
		++res;
		return ;
	}
	if (r >= n)
	{
		return ;
	}
	for (int i = 0; i < n; ++i)
	{
		if (!flag[i] && dic[r][i])
		{
			flag[i] = 1;
			DFS(r + 1, k - 1);
			flag[i] = 0;
		}
	}
	DFS(r + 1, k);
}
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int k, i, j;
	char ch;
 
	while (1)
	{
		scanf ("%d %d%*c", &n, &k);
		if (n == -1 && k == -1)
			break;
		for (i = 0; i < n; ++i)
		{
			for (j = 0; j < n; ++j)
			{
				ch = getchar();
				if (ch == '#')
					dic[i][j] = 1;
				else
					dic[i][j] = 0;
			}
			getchar();
		}
		memset(flag, 0, sizeof(flag));
		res = 0;
		DFS(0, k);
		printf ("%d\n", res);
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 1321 棋盘问题[DFS]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.