迷宫最短路径问题解析
摘要: 有一个二维数组,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 胡满超 阅读(8785) |
评论 (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 胡满超 阅读(4813) |
评论 (2) 编辑