P1379 八数码难题

题目描述

在?3×3?的棋盘上，摆有八个棋子，每个棋子上标有?1?至?8?的某一数字。棋盘中留有一个空格，空格用?0?来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为?123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用?0?表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

输入输出样例

输入 #1复制

283104765

输出 #1复制

4

说明/提示

样例解释

图中标有?0?的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

解析：

1.最短步骤想到使用bfs，用string来记录当前的状态，遍历状态。

注意：string 下角标是从0开始的，x = dx/3 , y = dy%3; 为真实九宫格的坐标。九宫格坐标是从（0，0）开始的。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
unordered_map<string,int> d;
queue<string> q;
int dx[4] ={-1,0,1,0};
int dy[4] = {0,1,0,-1};

int bfs(string str)
{
	q.push(str);
	string end="123804765";
	while(q.size())
	{
		string s = q.front();
		q.pop();
		if(s==end) return d[s];
		int k = s.find('0');
		int x = k/3,y = k%3;
		for(int i = 0;i < 4;i++)
		{
			int a = x+dx[i],b = y + dy[i];
			if(a<0||a>=3||b<0||b>=3) continue;
			int dis = d[s];
			swap(s[k],s[a*3 + b]);
			if(!d.count(s))//交换 
				d[s] = dis+1,q.push(s);
			swap(s[k],s[a*3+b]);//还原			
		}
	}	
} 
int main()
{
	string s;
	cin >> s;
	cout << bfs(s)<<endl;	
	return 0;
}

时间复杂度为：O()

使用A*算法进行优化。

A算法给出了评价函数的定义： f(n) = g(n) + h(n)
其中，n为待评价的节点；g(n)为从初始节点s到节点n的最佳路径耗散值的估计值；h(n)为从节点n到目标节点t的最佳路径耗散值的估计值，称为启发函数；f(n)为从初始节点s经过节点n到达目标节点的最佳路径耗散值的估计值，成为评价函数，我们每次从叶节点选出f(n)最小的节点扩展。
?

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> d;
string goal = "123804765";
int gx[] = {-1,0,0,0,1,2,2,2,1};
int gy[] = {-1,0,1,2,2,2,1,0,0};
int dx[4] ={-1,0,1,0};
int dy[4] = {0,1,0,-1};
int f(string s)
{ // 每个数字到目的地的坐标 
	int res = 0;
	for(int i = 0;i < 9;i++)
	{
		int t = s[i]-'0';
		if(t) res+= abs(i/3 - gx[t]) + abs(i%3-gy[t]);
	}
	return res;
}
int bfs(string str)
{
	unordered_map<string,int> d;
	priority_queue<pair<int,string>> q;//默认大根堆 ，我们只需要取负数，小的数就会在上面 
	q.push({-f(str),str});
	d[str] = 0;
	while(q.size())
	{
		auto a = q.top();
		q.pop();
		string s = a.second;
		if(s== goal) return d[s]; // d 记录现实的 状态 f为理想状态下 曼哈顿距离 
		int k = s.find('0');
		int x = k /3,y = k%3;
		for(int i = 0;i < 4;i++)
		{
			int a = x+dx[i],b = y + dy[i];
			if(a<0|| a>=3||b<0|| b>=3) continue;
			string t = s;
			swap(t[k],t[a*3+b]);
			if(!d.count(t))
			{
				d[t] = d[s]+1,q.push({-(d[t] + f(t)),t});
			}
		}
	}
} 
int main()
{
	string s;
	cin >> s;
	cout << bfs(s)<<endl;	
	return 0;
}