?? main.cpp
字號(hào):
#include <iostream>
#define SqureEdge 3
using namespace std;
struct NumNodeInfo
{
char NumEle[SqureEdge][SqureEdge];//由數(shù)字1、2、3、4、5、6、7、8、0構(gòu)成，0代表空值
NumNodeInfo *pChildNode[4];
bool isActive;//是否激活
};
//棧用于存儲(chǔ)最終搜尋到的路徑中的節(jié)點(diǎn)指針
struct NodeStack
{
NumNodeInfo *pNeededNode;
NodeStack *pNext;
};
/************************************************************************/
/* 函數(shù)：初始化節(jié)點(diǎn)指針 */
/* 參數(shù)：OriPosx,OriPoy為原節(jié)點(diǎn)的0的坐標(biāo),DesPosx,DesPosy */
/* 為目標(biāo)位置0的坐標(biāo),pOriNode為原節(jié)點(diǎn)指針,pDesNode為目標(biāo)節(jié)點(diǎn)指針 */
/************************************************************************/
void InitNode(int OriPosx,int OriPosy,int DesPosx,int DesPosy,NumNodeInfo *pOriNode,NumNodeInfo *pDesNode)
{
char temp;
int i,j;
for(i=0;i<4;i++)
pDesNode->pChildNode[i]=NULL;
pDesNode->isActive=true;
for(i=0;i<SqureEdge;i++)
for(j=0;j<SqureEdge;j++)
pDesNode->NumEle[i][j]=pOriNode->NumEle[i][j];
temp=pDesNode->NumEle[DesPosx][DesPosy];
pDesNode->NumEle[DesPosx][DesPosy]=pDesNode->NumEle[OriPosx][OriPosy];
pDesNode->NumEle[OriPosx][OriPosy]=temp;
}
/************************************************************************/
/* 函數(shù)：判斷兩個(gè)節(jié)點(diǎn)的內(nèi)容是否一致 */
/* 參數(shù)：*/
/* 返回值：如果一致返回true，否則返回false */
/************************************************************************/
bool isEqualNode(NumNodeInfo *pNodeA,NumNodeInfo *pNodeB)
{
int i,j;
for(i=0;i<SqureEdge;i++)
for(j=0;j<SqureEdge;j++)
if(pNodeA->NumEle[i][j]!=pNodeB->NumEle[i][j])
return false;
return true;
}
/************************************************************************/
/* 函數(shù)：檢測所要增加的節(jié)點(diǎn)是否已出現(xiàn)過 */
/* 參數(shù)：pTestNode為被檢測的節(jié)點(diǎn)指針,pTreeParNode為樹結(jié)構(gòu)的父節(jié)點(diǎn) */
/* 返回值：如果已出現(xiàn)過返回true，否則返回false */
/************************************************************************/
bool isExistedNode(NumNodeInfo *pTestNode,NumNodeInfo *pTreeParNode)
{
if(pTreeParNode==NULL)
return false;
if(isEqualNode(pTestNode,pTreeParNode))
return true;
else
if((pTreeParNode->pChildNode[0]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[0]))||(pTreeParNode->pChildNode[1]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[1]))
||(pTreeParNode->pChildNode[2]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[2]))||(pTreeParNode->pChildNode[3]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[3])))
return true;
else
return false;
}
/************************************************************************/
/* 函數(shù)：構(gòu)建當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn) */
/* 參數(shù)：CurNode 為當(dāng)前節(jié)點(diǎn)指針，ParNode為但錢節(jié)點(diǎn)的父節(jié)點(diǎn)指針, */
/* pSelfTreeRootNode為當(dāng)前樹的根節(jié)點(diǎn),pNeighborTreeRootNode為同步的*/
/* 鄰樹的根節(jié)點(diǎn) */
/* 返回值：如果所增加的節(jié)點(diǎn)在鄰樹中存在,則返回共同存在的2個(gè)節(jié)點(diǎn)中的一個(gè) */
/* 否則返回NULL */
/************************************************************************/
NumNodeInfo* BuildChildNode(NumNodeInfo *pCurNode,NumNodeInfo *pParNode,NumNodeInfo *pSelfTreeRootNode,NumNodeInfo *pNeighborTreeRootNode)
{
char temp[SqureEdge][SqureEdge];
int i,j;
int posx,posy;
for(i=0;i<SqureEdge;i++)
for(j=0;j<SqureEdge;j++)
if(pCurNode->NumEle[i][j]=='0')
{
posx=i;
posy=j;
}
NumNodeInfo *pChildTemp;
if(pParNode!=NULL)
{
for(i=0;i<SqureEdge;i++)
for(j=0;j<SqureEdge;j++)
temp[i][j]=pParNode->NumEle[i][j];
if (posx==0&&posy==0)
{
if(temp[posx][posy+1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx+1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
}
if (posx==0&&posy==SqureEdge-1)
{
if(temp[posx][posy-1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx+1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
}
if (posx==SqureEdge-1&&posy==SqureEdge-1)
{
if(temp[posx-1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx][posy-1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
}
if (posx==SqureEdge-1&&posy==0)
{
if(temp[posx][posy+1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx-1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL)
pCurNode->isActive=false;
return NULL;
}
}
if(posx==0)
{
if(temp[posx][posy-1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx+1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx][posy+1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
}
if(posy==0)
{
if(temp[posx-1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx][posy+1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx+1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
}
if(posx==SqureEdge-1)
{
if(temp[posx][posy-1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx-1][posy]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
return NULL;
}
if(temp[posx][posy+1]=='0')
{
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[0]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
pChildTemp=new NumNodeInfo;
InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
if(isExistedNode(pChildTemp,pSelfTreeRootNode))
delete pChildTemp;
else
{
pCurNode->pChildNode[1]=pChildTemp;
if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
return pChildTemp;
}
if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
pCurNode->isActive=false;
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -