迷宮最短路徑問題解析
摘要: 有一個(gè)二維數(shù)組，0表示路，-1表示墻，求其中任意兩點(diǎn)的最短路徑。
我們先看，怎么求一條路徑：求兩點(diǎn)路徑是一個(gè)數(shù)據(jù)結(jié)構(gòu)上的典型的迷宮問題，很多數(shù)據(jù)結(jié)構(gòu)的書上都有介紹，解決辦法如下：
從一點(diǎn)開始出發(fā)，向四個(gè)方向查找，每走一步，把走過的點(diǎn)的值+1(即本節(jié)點(diǎn)值+1)，防止重復(fù)行走，并把走過的點(diǎn)壓入堆棧(表示路徑)，如果遇到墻、或者已走過的點(diǎn)則不能前進(jìn)，如果前方已經(jīng)無路可走，則返回，路徑退棧，這樣遞歸調(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
閱讀全文
posted @
2008-03-18 17:47 胡滿超 閱讀(8918) |
評論 (4) 編輯
為二維數(shù)組循環(huán)賦值
摘要: 曾經(jīng)遇到一個(gè)為二維數(shù)組循環(huán)賦值的問題，即賦值后的二維數(shù)組為如下情形：
當(dāng)時(shí)在網(wǎng)上找了一下答案，基本上都是1層大循環(huán)套4層小循環(huán)還實(shí)現(xiàn)的，感覺不夠優(yōu)雅。最近翻了一下數(shù)據(jù)結(jié)構(gòu)的書，看到迷宮問題受到了一點(diǎn)啟發(fā)，感覺同樣是實(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
閱讀全文
posted @
2008-03-04 10:30 胡滿超 閱讀(4835) |
評論 (2) 編輯