有一個(gè)二維數(shù)組，0表示路，-1表示墻，求其中任意兩點(diǎn)的最短路徑。

我們先看，怎么求一條路徑：求兩點(diǎn)路徑是一個(gè)數(shù)據(jù)結(jié)構(gòu)上的典型的迷宮問(wèn)題，很多數(shù)據(jù)結(jié)構(gòu)的書(shū)上都有介紹，解決辦法如下：

從一點(diǎn)開(kāi)始出發(fā)，向四個(gè)方向查找，每走一步，把走過(guò)的點(diǎn)的值+1(即本節(jié)點(diǎn)值+1)，防止重復(fù)行走，并把走過(guò)的點(diǎn)壓入堆棧(表示路徑)，如果遇到墻、或者已走過(guò)的點(diǎn)則不能前進(jìn)，如果前方已經(jīng)無(wú)路可走，則返回，路徑退棧，這樣遞歸調(diào)用，直到找到終點(diǎn)為止。

迷宮如下圖所示：

struct Postion
{
    int _X, _Y;

    Postion(){}
    Postion(int X, int Y)
        : _X(X), _Y(Y){}
};

bool isCanGo(const int prePosValue,
             const int posX,
             const int posY)
{
    if (   posX < 0 || posX > 9        // 越界
        || posY < 0 || posY > 9        
        || maze[posX][posY] == -1    // 墻
        || maze[posX][posY] >= 1)    // 走過(guò)
    {
        return false;
    }

    return true;
}


stack<Postion> path__;            //路徑
        
Postion offset[4];                //路徑

bool shortestPath(stack<Postion> &path,
                  const Postion &start,
                  const Postion &end)
{
    if (   start._X == end._X 
        && start._Y == end._Y)
    {
        path__ = path;
        return true;
    }
    
    for (int i = 0; i < 4; i++)
    {
        int nNextPos_X = start._X + offset[i]._X;
        int nNextPos_Y = start._Y + offset[i]._Y;

        if (isCanGo(maze[start._X][start._Y], nNextPos_X, nNextPos_Y))
        {
            maze[nNextPos_X][nNextPos_Y] = maze[start._X][start._Y] + 1;

            path.push(Postion(nNextPos_X, nNextPos_Y));

            if (shortestPath(path, Postion(nNextPos_X, nNextPos_Y), end))
                return true;

            path.pop();
        }
    }

    return false;
}

int main(int argc, char* argv[])
{
    offset[0]._X = -1;    offset[0]._Y = 0;    // 上
    offset[1]._X = 1;    offset[1]._Y = 0;    // 下
    offset[2]._X = 0;    offset[2]._Y = -1;    // 左
    offset[3]._X = 0;    offset[3]._Y = 1;    // 右

    printMat(maze);


    Postion start(2, 1), end(6, 8);
    maze[start._X][start._Y] = 1;            // 置起點(diǎn)值1, 防止走回起點(diǎn)
    shortestPath(stack<Postion>(), start, end);

    printPath(path__);
    printMat(maze);

    return 0;
}

這時(shí)，我們經(jīng)過(guò)運(yùn)算，到達(dá)終點(diǎn)，有44步之多。如果我們調(diào)整調(diào)用offset的順序，即先左右，后上下，可能會(huì)得到更短的路徑，但無(wú)法確保在任何情況下都能得到最短路徑。

得到最短路徑的方法，解決方法如下：

每走一步，就對(duì)前方的節(jié)點(diǎn)賦值為此節(jié)點(diǎn)+1，走過(guò)的路徑也可以重復(fù)行走。但有一個(gè)條件，就是本節(jié)點(diǎn)+1必須小于已走過(guò)的節(jié)點(diǎn)的權(quán)值(墻不能走)，這樣走遍所有的節(jié)點(diǎn)，記錄最短的路徑。

主要修改了以下兩個(gè)函數(shù)：

bool isCanGo(const int prePosValue,
             const int posX,
             const int posY)
{
    if (   posX < 0 || posX > 9        // 越界
        || posY < 0 || posY > 9        
        || maze[posX][posY] == -1)    // 墻
    {
        return false;
    }

    if (maze[posX][posY] == 0)    // 未走過(guò)
        return true;
    else                        // 更近的路徑
        return (prePosValue + 1) < maze[posX][posY];
}

void shortestPath(stack<Postion> &path,
                  const Postion &start,
                  const Postion &end)
{
    if (   start._X == end._X 
        && start._Y == end._Y)
    {
        if (path.size() < path__.size() || path__.empty())    // 更短的路徑
            path__ = path;
        return;
    }
    
    for (int i = 0; i < 4; i++)
    {
        int nNextPos_X = start._X + offset[i]._X;
        int nNextPos_Y = start._Y + offset[i]._Y;

        if (isCanGo(maze[start._X][start._Y], nNextPos_X, nNextPos_Y))
        {
            maze[nNextPos_X][nNextPos_Y] = maze[start._X][start._Y] + 1;

            path.push(Postion(nNextPos_X, nNextPos_Y));

            shortestPath(path, Postion(nNextPos_X, nNextPos_Y), end);

            path.pop();
        }
    }
}
 

我上傳了兩個(gè)工程，求一條路徑的程序點(diǎn)此下載，求最短路徑的程序點(diǎn)此下載。

文章結(jié)束！愿它對(duì)您有所幫助。