1. 首页
  2. 文章中心
  3. Other

拼图3x3最短路径

31 阅读 0 评论
我是靠谱客的博主 无私蚂蚁，最近开发中收集的这篇文章主要介绍拼图3x3最短路径，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思想：空白块在不同的位置，走不同的路线。

每走一步，记录一下该图是否走到过。

使用广度遍历法来找最优解。

广度遍历：使用数组，9!=362880，用362880完全可以装完所有的图形

使用bitmap来保存该图形是否到过。0-8表示图形，用3bit表示一个小块，使用1bit表示0在低位还是高位，4bit表示0所处位置。一个图形保存在一个u32中就好了。

所以bitmap的大小事28bit，0xfffffff/8+1=1ffffff=32M byte。

每个数据保存父节点和图形，方便于逆推出路径。

struct pingtu
{
    pingtu *parent;
    u32 pingtuData;
};




#####################################################################################################


头文件jtt_typeDef.h

#ifndef JTT_TYPE_DEFINE

#define JTT_TYPE_DEFINE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef signed char s8;
typedef signed short s16;
typedef signed int s32;
typedef long long s64;
#define DEBUG_PRINTF_JTT_ENABLE    1
#if DEBUG_PRINTF_JTT_ENABLE
    #define DEBUG_PRINTF_JTT(fmt,arg...) printf(fmt,##arg)
#else
    #define DEBUG_PRINTF_JTT(fmt,arg...) do {}while(0)
#endif

#endif


文件main:

#include <stdio.h>
#include <math.h>
#include "jtt_typeDef.h"

#include <sys/time.h>
#include <unistd.h>


/*
28-31位表示0的位置，
27位表示0在低=0,0在高表示1，区分0和8
0-2,3-5，...，24-26表示0-8的数，其中0与8都位0
*/

#define ZERO_POINT_BEGIN    28
#define SET_ZERO_P(d,v)        {d &= ~(0xf<<ZERO_POINT_BEGIN);d |= (v<<ZERO_POINT_BEGIN);}

#define BIT_27        27
#define GET_MAX(a,b)    (a>b?a:b)
#define GET_MIN(a,b)    (a>b?b:a)
#define TREE_MAX_LEN    400000
#define DATA_IN_0_8(d)        (d >= 0 && d <=8)
#define SET_DATA_BIT(d,i)        (d |= (1<<i))
#define RESET_DATA_BIT(d,i)        (d &= ~(1<<i))
#define POINTER_TO_REAL_ADD(i)    (i * 3)

static const int bitmapLen = 0xfffffff / 8 + 1;
const u32 inputNum = 421038657;
const u32 outputNum = 78321654;

struct pingtu
{
    pingtu *parent;
    u32 pingtuData;
};

bool setOneBitOfBitMap(u32 setN, u8 *bmap, int maxLen)
{
    int flag = 0;
    u32 da,db;
    
    setN &= 0xfffffff;
    
    da = setN / 8;
    db = setN % 8;

    bmap[da] |= (1 << db);
    return true;
}

bool detectBitMapSet(u32 setN, u8 *bmap, int maxLen)
{
    int flag = 0;
    u32 da,db;
    setN &= 0xfffffff;
    da = setN / 8;
    db = setN % 8;
    
    if(bmap[da] & (1 << db))
    {
        return true;
    }
    return false;
}

void moveZeroToNext(const u32 inN, u32 &outN, int zP, int nP)
{
    int pb = GET_MAX(zP, nP);
    int pl = GET_MIN(zP, nP);
    outN = inN;
    for(int i = pl; i <= pb; i++)
    {
        if((inN & (7 << POINTER_TO_REAL_ADD(i))) == 0 && i != zP)
        {
            if(inN & (1 << BIT_27))
            {
                outN &= ~(1 << BIT_27);
            }
            else
            {
                outN |= (1 << BIT_27);
            }
            break;
        }
    }
    u32 t = ((inN >> POINTER_TO_REAL_ADD(nP)) & 0x7);
//    DEBUG_PRINTF_JTT("[Surpass:z=%u,n=%u]%s,%dn", zP, nP, __FILE__, __LINE__);
//    DEBUG_PRINTF_JTT("[Surpass:t=%u]%s,%dn", t, __FILE__, __LINE__);
    outN |= (t << POINTER_TO_REAL_ADD(zP));
    outN &= ~(0x7 << POINTER_TO_REAL_ADD(nP));

    SET_ZERO_P(outN,nP);
    //outN &= ~(0xf << ZERO_POINT_BEGIN);
    //outN |= (nP << ZERO_POINT_BEGIN);
//    DEBUG_PRINTF_JTT("[Surpass:i=%x,o=%x]%s,%dn", inN, outN, __FILE__, __LINE__);
}


bool findTheWay(u32 inN, u32 outN[4], int &outl)
{
    int zeroP = (inN >> ZERO_POINT_BEGIN);
    if(zeroP >= 9)
    {
        DEBUG_PRINTF_JTT("[Surpass:]%s,%dn", __FILE__, __LINE__);
        return false;
    }
    int i = zeroP;
    outl = 0;
    if(i % 3 != 0 && DATA_IN_0_8(i - 1))
    {
        moveZeroToNext(inN, outN[outl], i, i - 1);
        outl++;
    }
    if((i + 1) % 3 != 0 && DATA_IN_0_8(i + 1))
    {
        moveZeroToNext(inN, outN[outl], i, i + 1);
        outl++;
    }
    if(DATA_IN_0_8(i - 3))
    {
        moveZeroToNext(inN, outN[outl], i, i - 3);
        outl++;
    }    
    if(DATA_IN_0_8(i + 3))
    {
        moveZeroToNext(inN, outN[outl], i, i + 3);
        outl++;
    }
    return true;
/*    switch(i)
    {
        case 0:
            moveZeroToNext(inN, outN[0], i, 1);
            moveZeroToNext(inN, outN[1], i, 3);
            break;
        case 1:
            moveZeroToNext(inN, outN[0], i, 0);
            moveZeroToNext(inN, outN[1], i, 2);
            moveZeroToNext(inN, outN[2], i, 4);
            break;
        case 2:
            moveZeroToNext(inN, outN[0], i, 1);
            moveZeroToNext(inN, outN[1], i, 5);
            break;
        case 3:
            moveZeroToNext(inN, outN[0], i, 0);
            moveZeroToNext(inN, outN[1], i, 4);
            moveZeroToNext(inN, outN[2], i, 6);
            break;
        case 4:
            moveZeroToNext(inN, outN[0], i, 1);
            moveZeroToNext(inN, outN[1], i, 3);
            moveZeroToNext(inN, outN[2], i, 5);
            moveZeroToNext(inN, outN[4], i, 6);
            break;
        case 5:
            moveZeroToNext(inN, outN[0], i, 2);
            moveZeroToNext(inN, outN[1], i, 4);
            moveZeroToNext(inN, outN[2], i, 8);
            break;
        case 6:
            moveZeroToNext(inN, outN[0], i, 3);
            moveZeroToNext(inN, outN[1], i, 7);
            break;
        case 7:
            moveZeroToNext(inN, outN[0], i, 4);
            moveZeroToNext(inN, outN[1], i, 6);
            moveZeroToNext(inN, outN[2], i, 8);
            break;
        case 8:
            moveZeroToNext(inN, outN[0], i, 5);
            moveZeroToNext(inN, outN[1], i, 8);
            break;
    }
*/
}

bool convertIntToMyType(u32 ind, u32 &od)
{
    u16 bitmap = 0;
    u32 temp;
    int  i;
    int flagz = 0;
    od = 0;
    for(i = 0; i < 9; i++)
    {
        temp = ind % 10;
        ind /= 10;
        
        SET_DATA_BIT(bitmap, temp);
                
        if(temp == 0)// || temp == 8)
        {
            if(flagz == 0)
            {
                flagz = 1;
            }
            else if(flagz == 2)
            {
                SET_DATA_BIT(od, BIT_27);
                flagz = 3;
            }
            else
            {
                return false;
            }
            od |= (i << ZERO_POINT_BEGIN);
        }
        if(temp == 8)// || temp == 8)
        {
            if(flagz == 0)
            {
                flagz = 2;
            }
            else if(flagz == 1)
            {
                DEBUG_PRINTF_JTT("[Surpass:]%s,%dn", __FILE__, __LINE__);
                RESET_DATA_BIT(od, BIT_27);
                flagz = 3;
            }
            else
            {
                DEBUG_PRINTF_JTT("[Surpass:]%s,%dn", __FILE__, __LINE__);
                return false;
            }
        }
        temp &= 0x7;
        od |= (temp << POINTER_TO_REAL_ADD(i));
    }
    
    if(bitmap != 0x1ff)
    {
        DEBUG_PRINTF_JTT("[Surpass:]%s,%dn", __FILE__, __LINE__);
        return false;
    }
    return true;
}

void convertMyTypeToInt(u32 ind, u32 &od, int &zPoint, int &zAtH)
{
    u32 temp;
    od = 0;
    for(int i = 0; i < 9; i++)
    {
        if(((ind >> POINTER_TO_REAL_ADD(i)) & 0x7) == 0 && ((ind >> ZERO_POINT_BEGIN) != i))
        {
            temp = 8;
        }
        else
        {
            temp = ((ind >> POINTER_TO_REAL_ADD(i)) & 0x7);
        }
        od += temp * pow(10, i);
    }
    
    zPoint = (ind >> ZERO_POINT_BEGIN);
    zAtH = (ind >> BIT_27) & 0x1;
}
int main()
{
    u32 tempWay[4];
    int getWayLen;
    
    u32 tempDebugD;
    int tempzPoint;
    int tempzAtHighF;

    int findThePointF = 0;

    pingtu *tem;// = &treeBreadthTraversal[readInd];
    int i = 0;

    // 2^28 = 0XFFFFFFF, bitmap = 2^25 = 0x1ffffff = 33554431
    u8 *bitmapBuf = NULL;
    //9! = 362880
    pingtu *treeBreadthTraversal = NULL;
    
    int writeInd = 1, readInd = 0;


    u64 timenow,timebegin;
    struct timeval tv;
    struct timezone tz;
    gettimeofday (&tv, &tz);
    timebegin = tv.tv_sec * 1000000 + tv.tv_usec;

    bitmapBuf = new u8[bitmapLen];
    if(bitmapBuf == NULL)
    {
        DEBUG_PRINTF_JTT("fail malloc buf = %dn", bitmapLen);
        goto returnMain;
    }
    else
    {
        DEBUG_PRINTF_JTT("malloc ok buf = %dn", bitmapLen);
    }
    memset(bitmapBuf, 0, bitmapLen);

    treeBreadthTraversal = new pingtu[TREE_MAX_LEN];
    if(treeBreadthTraversal == NULL)
    {
        DEBUG_PRINTF_JTT("fail malloc buf = %dn", TREE_MAX_LEN);
        goto returnMain;
    }
    else
    {
        DEBUG_PRINTF_JTT("malloc ok buf = %dn", TREE_MAX_LEN);
    }

    DEBUG_PRINTF_JTT("[Surpass:input=%u]%s,%dn", inputNum, __FILE__, __LINE__);
    if(convertIntToMyType(inputNum, treeBreadthTraversal[0].pingtuData))
        DEBUG_PRINTF_JTT("[Surpass:%X]%s,%dn", treeBreadthTraversal[0].pingtuData, __FILE__, __LINE__);
    treeBreadthTraversal[0].parent = NULL;
    convertMyTypeToInt(treeBreadthTraversal[0].pingtuData, tempDebugD, tempzPoint, tempzAtHighF);
    DEBUG_PRINTF_JTT("[Surpass:%09u,%d,%s]%s,%dn", tempDebugD, tempzPoint, (tempzAtHighF?"h":"l"), __FILE__, __LINE__);
    
    while(readInd < writeInd)
    {
        if(!findTheWay(treeBreadthTraversal[readInd].pingtuData, tempWay, getWayLen))
        {
            DEBUG_PRINTF_JTT("[Surpass:err]%s,%dn", __FILE__, __LINE__);
            goto returnMain;
        }
        //DEBUG_PRINTF_JTT("[Surpass:%d]%s,%dn", getWayLen, __FILE__, __LINE__);
        for(int i = 0; i < getWayLen; i++)
        {
            //DEBUG_PRINTF_JTT("[Surpass:%09u,%d,%s]%s,%dn", tempDebugD, tempzPoint, (tempzAtHighF?"h":"l"), __FILE__, __LINE__);

            if(!detectBitMapSet(tempWay[i], bitmapBuf, bitmapLen))
            {
                if(writeInd < TREE_MAX_LEN)
                {
                    setOneBitOfBitMap(tempWay[i], bitmapBuf, bitmapLen);
                    treeBreadthTraversal[writeInd].pingtuData = tempWay[i];
                    treeBreadthTraversal[writeInd].parent = &treeBreadthTraversal[readInd];
                    
                    writeInd++;
                }
                else
                {
                    DEBUG_PRINTF_JTT("[Surpass:err]%s,%dn", __FILE__, __LINE__);
                    goto returnMain;
                }
                
                convertMyTypeToInt(tempWay[i], tempDebugD, tempzPoint, tempzAtHighF);
                if(tempDebugD == outputNum)
                {
                    findThePointF = 1;
                    goto finishFind;
                }
                
            }
            
        }
        readInd++;
    }

    //DEBUG_PRINTF_JTT("[Surpass:%p,]%s,%dn", treeBreadthTraversal[readInd].parent, __FILE__, __LINE__);
finishFind:

    gettimeofday (&tv, &tz);
    timenow= tv.tv_sec * 1000000 + tv.tv_usec;
    
    DEBUG_PRINTF_JTT("[Surpass:time=%llu, ind=%u]%s,%dn", timenow - timebegin, writeInd, __FILE__, __LINE__);
    if(findThePointF)
    {
        DEBUG_PRINTF_JTT("[Surpass:find!]%s,%dn", __FILE__, __LINE__);
    }
    else
    {
        DEBUG_PRINTF_JTT("[Surpass:not find!]%s,%dn", __FILE__, __LINE__);
    }
    
    tem = &treeBreadthTraversal[writeInd - 1];
    i = 0;
    while(tem != NULL)
    {
        convertMyTypeToInt(tem->pingtuData, tempDebugD, tempzPoint, tempzAtHighF);
        DEBUG_PRINTF_JTT("[Surpass:%09u,%d,%s]%s,%dn", tempDebugD, tempzPoint, (tempzAtHighF?"h":"l"), __FILE__, __LINE__);
        tem = tem->parent;
        i++;
    }
    DEBUG_PRINTF_JTT("[Surpass:i=%d]%s,%dn", i, __FILE__, __LINE__);
returnMain:
    if(bitmapBuf)
        delete bitmapBuf;
    if(treeBreadthTraversal)
        delete treeBreadthTraversal;
    return 1;
}


最后

以上就是无私蚂蚁为你收集整理的拼图3x3最短路径的全部内容，希望文章能够帮你解决拼图3x3最短路径所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(21)

相关文章

poj1797 spfa 最短路
poj1797 spfa 最短路
poj-2253-poj-1797_最短路练习概述分析与思路代码小结
poj-2253-poj-1797_最短路练习概述分析与思路代码小结
POJ - 3660 Cow Contest(最短路变形+闭包传递)
POJ - 3660 Cow Contest(最短路变形+闭包传递)
POJ_1062_最短路变形
POJ_1062_最短路变形
拼图3x3最短路径
拼图3x3最短路径
poj3660——Cow Contest【最短路】
poj3660——Cow Contest【最短路】
poj 1797(最短路变形)
poj 1797(最短路变形)
POJ 1797 最短路
POJ 1797 最短路

评论列表共有 0 条评论

立即
投稿
返回
顶部