迷宮最短路徑問題解析
摘要: 有一個二維數組，0表示路，-1表示墻，求其中任意兩點的最短路徑。
我們先看，怎么求一條路徑：求兩點路徑是一個數據結構上的典型的迷宮問題，很多數據結構的書上都有介紹，解決辦法如下：
從一點開始出發，向四個方向查找，每走一步，把走過的點的值+1(即本節點值+1)，防止重復行走，并把走過的點壓入堆棧(表示路徑)，如果遇到墻、或者已走過的點則不能前進，如果前方已經無路可走，則返回，路徑退棧，這樣遞歸調用，直到找到終點為止。
迷宮如下圖所示：
從(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 胡滿超 閱讀(8882) |
評論 (4) 編輯
為二維數組循環賦值
摘要: 曾經遇到一個為二維數組循環賦值的問題，即賦值后的二維數組為如下情形：
當時在網上找了一下答案，基本上都是1層大循環套4層小循環還實現的，感覺不夠優雅。最近翻了一下數據結構的書，看到迷宮問題受到了一點啟發，感覺同樣是實現這個功能，如下代碼要優雅一些：
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 胡滿超 閱讀(4823) |
評論 (2) 編輯