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