随笔 - 89  文章 - 118  trackbacks - 0
<2008年3月>
2425262728291
2345678
9101112131415
16171819202122
23242526272829
303112345

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

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 胡满超 阅读(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)  编辑