放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

AOJ 0121: Seven Puzzle 《挑战程序设计竞赛(第2版)》练习题答案

挑战程序设计竞赛第二版.jpg

2.1 最基础的“穷竭搜索” 广度优先搜索

0121: Seven Puzzle

有一个4*2的方框,里面随机填充着0-7这8个数。每次只有0可以交换相邻格子里的数。比如:

可以交换为

也可以交换为

,最终希望8个数整齐地排列为

求最小的交换次数。

 

输入:

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0

输出:

0
1
28

跑个题,这题的日文注解在下一页,如果你喜欢日语的话欢迎翻页看原题注解。

思路:与前几题的bfs不同,这次的bfs没有明确的移动对象,看似任意一个数都可以当成对象移动。把0作为移动对象,那么0在地图中漫游所有的格子得到的肯定就是问题的解空间。由于题目的输入是多个case,如果对每个case都运行一遍bfs就会TLE。这时我们祭出dp技能,只需要一次bfs就将解空间算出来,以后每个case只要到解空间中去找就行了。

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

map<string, int> dp;
int direction[4] = { 1, -1, 4, -4 };

//************************************
// Method:    bfs
// FullName:  bfs
// Access:    public 
// Returns:   void
// Qualifier: 让0漫游整个字串
//************************************
void bfs()
{
	queue<string> que;
	que.push("01234567");
	dp["01234567"] = 0;
	while (!que.empty())
	{
		string now = que.front(); que.pop();
		// p是'0'的位置
		int p = 0;
		for (int j = 0; j < 8; ++j)
		{
			if (now[j] == '0')
			{
				p = j;
				break;
			}
		}

		for (int i = 0; i < 4; ++i)
		{
			int n = p + direction[i];
			if (0 <= n && n < 8 && 
				!(p == 3 && i == 0) && // 右上角不能再往右了
				!(p == 4 && i == 1))   // 左下角不能再往左了
			{
				string next = now;
				swap(next[p], next[n]);
				if (dp.find(next) == dp.end())
				{
					dp[next] = dp[now] + 1;
					que.push(next);
				}
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

	bfs();
	string line;
	while (getline(cin, line))
	{
		line.erase(remove(line.begin(), line.end(), ' '), line.end());
		cout << dp[line] << endl;
	}

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 0121: Seven Puzzle 《挑战程序设计竞赛(第2版)》练习题答案

评论 10

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

    并不是随便抓一个当作移动对象,比如02134567就还是0,而是0作为空格,是可交换移动的

    阿不管的啦5年前 (2019-04-21)回复
  2. #3

    作者你好,能不能解释下这句dp.find(next) == dp.end()是什么意思 我对STL的东西不怎么懂 谢谢!

    gdutzhuhui8年前 (2016-03-31)回复
    • dp.find(next) == dp.end()表示不存在 我还是不理解 能详细点吗 不胜感激

      gdutzhuhui8年前 (2016-03-31)回复
      • 我懂了。很巧妙!学习 了!

        gdutzhuhui8年前 (2016-03-31)回复
  3. #2

    谢谢作者的代码,我可以问一下
    if (dp.find(next) == dp.end())
    {
    dp[next] = dp[now] + 1;
    que.push(next);
    }
    这一段的意思是不是表示如果他是一个新找到的字符串(说明是最早找到的,所以在map里面是末尾),那我们就入队?

    Philip9年前 (2015-09-26)回复
    • dp.find(next) == dp.end()表示不存在

      hankcs9年前 (2015-09-26)回复
  4. #1

    line.erase(remove(line.begin(), line.end(), ‘ ‘), line.end());这个的有什么用

    奥特曼9年前 (2015-02-22)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》