放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

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版)》练习题答案

分享到:更多 ()

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    这题是poj3050,不是3035,google会搜不到你的博客的。今晚独立完成两题感觉好爽,就是速度太慢,我也是用dfs可是我做这题的时候用g++竟然超时了,用c++700多ms

    奥特曼3年前 (2015-02-26)回复
    • 谢谢指正。慢慢来,g++是有会超时。

      hankcs3年前 (2015-02-26)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机