?? main.cpp
字號:
#include <iostream>
#define SqureEdge 3
using namespace std;
struct NumNodeInfo
{
char NumEle[SqureEdge][SqureEdge];//由數字1、2、3、4、5、6、7、8、0構成，0代表空值
NumNodeInfo *pChildNode[4];
bool isActive;//是否激活
};
//棧用于存儲最終搜尋到的路徑中的節點指針
struct NodeStack
{
NumNodeInfo *pNeededNode;
NodeStack *pNext;
};
/************************************************************************/
/* 函數：初始化節點指針 */
/* 參數：OriPosx,OriPoy為原節點的0的坐標,DesPosx,DesPosy */
/* 為目標位置0的坐標,pOriNode為原節點指針,pDesNode為目標節點指針 */
/************************************************************************/
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;
}
/************************************************************************/
/* 函數：判斷兩個節點的內容是否一致 */
/* 參數：*/
/* 返回值：如果一致返回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;
}
/************************************************************************/
/* 函數：檢測所要增加的節點是否已出現過 */
/* 參數：pTestNode為被檢測的節點指針,pTreeParNode為樹結構的父節點 */
/* 返回值：如果已出現過返回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;
}
/************************************************************************/
/* 函數：構建當前節點的子節點 */
/* 參數：CurNode 為當前節點指針，ParNode為但錢節點的父節點指針, */
/* pSelfTreeRootNode為當前樹的根節點,pNeighborTreeRootNode為同步的*/
/* 鄰樹的根節點 */
/* 返回值：如果所增加的節點在鄰樹中存在,則返回共同存在的2個節點中的一個 */
/* 否則返回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;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -