題意: 題意就是八數(shù)碼,給了一個3 * 3 的矩陣,上面有八個數(shù)字,有一個位置是空的,每次空的位置可以和他相鄰的數(shù)字換位置,給你一些起始狀態(tài) ,給了一個最終狀態(tài),讓你輸出怎么變換才能達(dá)到目的.

思路: 首先我們先判斷一下可不可以達(dá)到最終目的,方法是根據(jù)逆序數(shù),只要終止?fàn)顟B(tài)和起始狀態(tài)的逆序數(shù)(空的位置不算)奇偶性相同就能,否則不能;

證明 :

加入當(dāng)前空的位置是i,針對3 * 3 的也就是八數(shù)碼問題(可能有別的數(shù)碼,根據(jù)奇偶性答案不同) 如果向前或向后移動的話 當(dāng)前的逆序數(shù)不變,如果像上移動的話有三種情況, 移動過來的這個數(shù)比那兩個數(shù)都大,逆序數(shù) - 2 ,移動過來的這個數(shù)比那兩個數(shù)都小 逆序數(shù) + 2,比一個大,比另一個小,逆序數(shù) + 1 - 1 不變,所以怎么移動逆序數(shù)奇偶性不變,所以只有起始狀態(tài)可終止?fàn)顟B(tài)逆序數(shù)奇偶性相同才能轉(zhuǎn)換..

解決了判斷,剩下的就是輸出方法了,直接暴搜會TLE出"翔"來(測試數(shù)據(jù)太多),我們觀察會發(fā)現(xiàn),題目最終的目的地是同一個狀態(tài),無論什么最后都要到題目中給的那個終點,那么我們可以直接以終點為起點,遍歷一邊所有狀態(tài),然后把它存起來,等問的時候我們只要把存的方法變換一下就ok了,首先把整個序列顛倒過來,因為我們是反向打表,然后相應(yīng)的 上 變 下 下 變 上 ... 因為是反向搜索..然后輸出來就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("unsolvable\n");
? ? ? ? ?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] = '\0';
? ? ? puts(ans);
? ? ??
? ?}
? ?return 0;
} ? ??
? ?

總結(jié)

以上是生活随笔為你收集整理的hdu1043 经典的八数码问题 逆向bfs打表 + 逆序数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。