hdu1043 经典的八数码问题逆向bfs打表 + 逆序数

71 阅读 0 评论 47 点赞

我是靠谱客的博主听话樱桃，最近开发中收集的这篇文章主要介绍hdu1043 经典的八数码问题逆向bfs打表 + 逆序数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意: 题意就是八数码,给了一个3 * 3 的矩阵,上面有八个数字,有一个位置是空的,每次空的位置可以和他相邻的数字换位置,给你一些起始状态 ,给了一个最终状态,让你输出怎么变换才能达到目的.

思路: 首先我们先判断一下可不可以达到最终目的,方法是根据逆序数,只要终止状态和起始状态的逆序数(空的位置不算)奇偶性相同就能,否则不能;

证明 :

加入当前空的位置是i,针对3 * 3 的也就是八数码问题(可能有别的数码,根据奇偶性答案不同) 如果向前或向后移动的话当前的逆序数不变,如果像上移动的话有三种情况, 移动过来的这个数比那两个数都大,逆序数 - 2 ,移动过来的这个数比那两个数都小逆序数 + 2,比一个大,比另一个小,逆序数 + 1 - 1 不变,所以怎么移动逆序数奇偶性不变,所以只有起始状态可终止状态逆序数奇偶性相同才能转换..

解决了判断,剩下的就是输出方法了,直接暴搜会TLE出"翔"来(测试数据太多),我们观察会发现,题目最终的目的地是同一个状态,无论什么最后都要到题目中给的那个终点,那么我们可以直接以终点为起点,遍历一边所有状态,然后把它存起来,等问的时候我们只要把存的方法变换一下就ok了,首先把整个序列颠倒过来,因为我们是反向打表,然后相应的上变下下变上 ... 因为是反向搜索..然后输出来就ok了, 这让我想起了以前做过的一道最短路,一群牛去一个地方开会,在回来问所有路径的最短和,路是单向的,我们只要直接以开会点为起点,跑两边最短路就ok了..想法是一样的.上代码.

//逆向BFS打表 AC

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<map>
#include<queue>

using namespace std;

typedef struct
{
int now_map[10];
string root;
int id0;
}NODE;

map<int ,string>ans_map;
map<int ,int>mk;
NODE xin ,tou;
char ans[800000];
int end_map[10] = {0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,0};

bool hash(int now[] ,string root)
{
int sum = 0 ,e = 1;
for(int i = 1 ;i <= 9 ;i ++)
{
sum += e * now[i];
e *= 10;
}
if(mk[sum])
return 1;
mk[sum] = 1;
ans_map[sum] = root;
return 0;
}

void DB_BFS()
{
for(int i = 1 ;i <= 9 ;i ++)
xin.now_map[i] = end_map[i];
xin.root = "";
xin.id0 = 9;
queue<NODE>q;
q.push(xin);
ans_map.clear();
mk.clear();
hash(xin.now_map ,"ud");
while(!q.empty())
{
tou = q.front();
q.pop();

if(tou.id0 >= 4)
{
xin = tou;
xin.root = tou.root + 'u';
xin.now_map[xin.id0] = tou.now_map[xin.id0-3];
xin.now_map[xin.id0-3] = 0;
xin.id0 -= 3;
if(!hash(xin.now_map ,xin.root))
{
q.push(xin);
}
}

if(tou.id0 <= 6)
{
xin = tou;
xin.root = tou.root + 'd';
xin.now_map[xin.id0] = tou.now_map[xin.id0+3];
xin.now_map[xin.id0+3] = 0;
xin.id0 += 3;
if(!hash(xin.now_map ,xin.root))
{
q.push(xin);
}
}

if(tou.id0 != 1 && tou.id0 != 4 && tou.id0 != 7)
{
xin = tou;
xin.root = tou.root + 'l';
xin.now_map[xin.id0] = tou.now_map[xin.id0-1];
xin.now_map[xin.id0-1] = 0;
xin.id0 --;
if(!hash(xin.now_map ,xin.root))
{
q.push(xin);
}
}

if(tou.id0 != 3 && tou.id0 != 6 && tou.id0 != 9)
{
xin = tou;
xin.root = tou.root + 'r';
xin.now_map[xin.id0] = tou.now_map[xin.id0+1];
xin.now_map[xin.id0+1] = 0;
xin.id0 ++;
if(!hash(xin.now_map ,xin.root))
{
q.push(xin);
}
}
}
}

int main ()
{
int i ,id0;
char str[5];
DB_BFS();
NODE A;
while(~scanf("%s" ,str))
{
if(str[0] == 'x')
{
A.id0 = 1;
A.now_map[1] = 0;
}
else
A.now_map[1] = str[0] - 48;
for(i = 2 ;i <= 9 ;i ++)
{
scanf("%s" ,str);
if(str[0] == 'x')
{
A.id0 = i;
A.now_map[i] = 0;
}
else
A.now_map[i] = str[0] - 48;
}

int sum = 0;
int ss = 0 ,e = 1;
for(i = 1 ;i <= 9 ;i ++)
{
ss += A.now_map[i] * e;
e *= 10;
if(!A.now_map[i])continue;
for(int j = 1 ;j < i ;j ++)
if(A.now_map[i] < A.now_map[j])
sum ++;
}
if(sum % 2)
{
printf("unsolvablen");
continue;
}

int l = ans_map[ss].length();
for(i = 0 ;i < l ;i ++)
{
char c = ans_map[ss][l-i-1];
if(c == 'u')
ans[i] = 'd';
if(c == 'd')
ans[i] = 'u';
if(c == 'l')
ans[i] = 'r';
if(c == 'r')
ans[i] = 'l';
}
ans[l] = '';
puts(ans);

}
return 0;
}