随笔 - 88  文章 - 118  trackbacks - 0
<2008年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

留言簿(15)

随笔分类(54)

随笔档案(88)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

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