POJ 3050 Hopscotch《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 穷竭搜索

POJ 3050 Hopscotch

在5 * 5的方格里跳房子，起点是任意位置。将跳过的数连起来组成一个5位数（前导零可能），问一共能组成多少个数字？

当前的状态可以定义为当前位置、当前数字长度、当前数字这三个要素，利用状态转移dfs即可遍历所有情况。对于数字的储存使用single key set可以轻松满足要求。

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

int map[5][5];
const int direction[4][2] = {
    { -1, 0 },
    { 1, 0 },
    { 0, -1 },
    { 0, 1 },
};

set<int> results;

void dfs(const int& x, const int& y, const int& step, const int& number)
{
	if (step == 5)
	{
		// 跳房子结束
		results.insert(number);
		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		int nx = x + direction[i][0];
		int ny = y + direction[i][1];
		if (0 <= nx && nx < 5 && 0 <= ny && ny < 5)
		{
			dfs(nx, ny, step + 1, number * 10 + map[nx][ny]);
		}
	}
}

int main(int argc, char *argv[])
{
	int i = 0;
	int j = 0;
    for (; i < 5; ++i)
    {
		for (j = 0;j < 5; ++j)
		{
			cin >> map[j][i];
		}
    }

	for (i = 0; i < 5; ++i)
    {
		for (j = 0;j < 5; ++j)
		{
			dfs(i, j, 0, map[i][j]);
		}
    }

	cout << results.size() << endl;
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3050 Hopscotch《挑战程序设计竞赛(第2版)》练习题答案