迷宮最短路徑問(wèn)題解析
摘要: 有一個(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)為止。
迷宮如下圖所示：
從(2, 1)到(6, 8)，程序如下所示：
struct Postion
{
int _X, _Y;
Postion(){}
Postion(int X, int Y)
: _X(X), _Y(Y){}
};
bool isCanGo(const int prePosValue,
con
閱讀全文
為二維數(shù)組循環(huán)賦值
摘要: 曾經(jīng)遇到一個(gè)為二維數(shù)組循環(huán)賦值的問(wèn)題，即賦值后的二維數(shù)組為如下情形：
當(dāng)時(shí)在網(wǎng)上找了一下答案，基本上都是1層大循環(huán)套4層小循環(huán)還實(shí)現(xiàn)的，感覺(jué)不夠優(yōu)雅。最近翻了一下數(shù)據(jù)結(jié)構(gòu)的書(shū)，看到迷宮問(wèn)題受到了一點(diǎn)啟發(fā)，感覺(jué)同樣是實(shí)現(xiàn)這個(gè)功能，如下代碼要優(yōu)雅一些：
const int ROW__ = 10;
const int COL__ = 10;
int mat[ROW__][COL__];
struct Position
{
int nRow;
int nCol;
};
void printMat(int mat[ROW__][COL__]);
int main(int argc, char* argv[])
{
Position offset[4];
offset[0].nRow = 0; offset[0].nCol = 1;
offs
閱讀全文