?? 算法 7.6.txt
字號:
算法 7.6
bool ShortestPath(int maze[][], int m, int n,Stack &S)
{
// 求m行n列的迷宮maze中從入口[0][0]到出口[m-1][n-1]的最短路徑,
// 若存在,則返回TRUE,此時(shí)棧S中從棧頂?shù)綏5诪樽疃搪窂剿?jīng)過的各
// 個(gè)方位;若該迷宮不通,則返回FALSE,此時(shí)棧S為空棧。
DLinkQueue Q;
bool visited[m][n];
InitQueue(Q); // 隊(duì)列初始化
for(i=0; i<m; i++) // 對訪問標(biāo)志數(shù)組置初值
for(j=0; j<n; j++) visited[i][j] = FALSE;
if (maze[0][0]!=0) return FALSE;
e.xpos = 0; e.ypos = 0; EnQueue(Q, e); // 入口頂點(diǎn)入隊(duì)列
found = FALSE;
while(!found && !QueueEmpty(Q)) {
GetHead(Q, curpos); // 取當(dāng)前的隊(duì)頭頂點(diǎn)curpos
for (v=0; v<8,!found; v++) { // 搜索8個(gè)方向的鄰接點(diǎn)
npos = NextPos(curpos, v);
// 類型為PosType的npos是搜索到的下一點(diǎn)
if (Pass(npos)) { // 如果下一點(diǎn)可走通則入隊(duì)列
EnQueue(Q, npos);
visited[npos.xpos][npos.ypos] = TRUE; // 置到訪標(biāo)志
}//if
if (npos.xpos=n-1 && npos.ypos=m-1) found=TRUE; // 找到出口
}//for
DeQueue(Q); // 出隊(duì)列,準(zhǔn)備從下一鄰接點(diǎn)搜索
}//while
if (found) {
InitStack(S); // 棧初始化
p = Q.rear; // 從出口頂點(diǎn)以pre指針為導(dǎo)向,反向查看
while(!p) {
Push(S,p->seat); // 把屬于最短路徑的頂點(diǎn)壓入棧中
p=p->pre;
}//while
return TRUE;
}//if
else return FALSE;
}//ShortestPath
在算法7.6中,Pass()為判斷迷宮通或阻的函數(shù)。
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -