POJ 1321 棋盘问题

这道题是一个纯粹的深度优先搜索,而且是其中最简单的一种:不需要判重。

/* 
 *	POJ 1321
 *	URL: http://poj.org/problem?id=1321
 *	Author: Ceeji Cheng
 *	Type: Depth First Search
 *	Status: Programing
 *	Visit http://ceeji.net/ for more information.
 *	2011-02-24 15:34
 */
 
#include <iostream>
#include <cstring>
#include <string>
 
using namespace std;
 
#define MAX_N 8
 
int matrix[MAX_N][MAX_N];
bool has[MAX_N];
int n, k, res = 0;
string ts;
 
void search(int p, int line)
{
	if (line >= n)
	{
		if (p == k)
			++res;
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		if (matrix[line][i] && !has[i])
		{
			has[i] = true;
			search(p + 1, line + 1);
			has[i] = false;
		}
	}
	search(p, line + 1);
}
 
int main (int argc, char const* argv[])
{
	while (cin >> n >> k && n != -1)
	{
		// clear the matrix.
		memset(matrix, 0, sizeof(matrix));
		// init.
		for (int i = 0; i < n; ++i)
		{
			cin >> ts;
			for (int j = 0; j < n; ++j)
				matrix[i][j] = ts[j] == '#' ? 1 : 0;
		}
		res = 0;
		search(0, 0);
		cout << res << endl;
	}
	return 0;
}

题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: