已解決

Rank: 1

2^#

發表於 2008-11-7 14:36 | 只看該作者

nextstep函数是判断当前所处位置（x，y）是否可以向前（返回1）、向左（返回2）、向右（返回3）、向后（返回4）

jy02453563

Rank: 1

3^#

發表於 2008-11-7 17:16 | 只看該作者

原帖由 freewave 於 2008-11-7 14:36 發表
nextstep函数是判断当前所处位置（x，y）是否可以向前（返回1）、向左（返回2）、向右（返回3）、向后（返回4）

我知道~但是我不知道讓怎麼改

if(input[x+1][y]=='.'){
d=1;}
if(input[x][y+1]=='.'){
d=2;}
if(input[x][y-1]=='.'){
d=3;}
if(input[x-1][y]=='.'){
d=4;}

複製代碼

是我自己加進去~但是跑不出來,不懂改><~用else if也不行...想不出來...

Newbie

中級會員

Rank: 2 Rank: 2

4^#

發表於 2008-11-7 17:39 | 只看該作者

原帖由 jy02453563 於 2008-11-7 17:16 發表

我知道~但是我不知道讓怎麼改 if(input[x+1][y]=='.'){
d=1;}
if(input[x][y+1]=='.'){
d=2;}
if(input[x][y-1]=='.'){
d=3;}
if(input[x-1][y]=='.'){
d=4;}是我自己加進去~但是跑不出來,不懂改>

第一步會行落第二層, 但第二步會上返去, 係nextstep內d先會等如2, 然後等如3, 最後等如4, 再轉回主程式, 會回到上層, 然後不斷重復.... (好似係)

Rank: 1

5^#

發表於 2008-11-7 17:50 | 只看該作者

要搜索迷宫有没有出路，就要遍历所有的路径，直到有一条能够走出去，可以通过递归来做。

ps：你的nextstep函数，只是判断从当前位置可以向哪里走，因为你设定了run<3000，所以不一定能够走出去的。

我要外出，如有需要周六可以给你提供个例子。

jy02453563

Rank: 1

6^#

發表於 2008-11-9 16:11 | 只看該作者

求救.......................

Rank: 1

7^#

發表於 2008-11-9 21:41 | 只看該作者

#include "stdafx.h"
#include <assert.h>
#include <vector>
#include<iostream.h>
#include<fstream.h>
#pragma warning(disable:4786)
/*
# 16 * 16 的迷宫, '.'表示可以行走， '*'不可以行走
(0,0)
|---------------------->(x direction)
|*.**************
|*........*******
|*.******.*******
|*...***..*******
|****.**.*.....**
|**...**.*.***.**
|**.***....***.**
|**..*..**.***.**
|***.*.*...***.**
|**..*.**.****.**
|**....**......**
|**.*.*****.*****
|*..*.*...*.*****
|*.**...*.*.*****
|*.******.*.*****
|********.*******
|
(y direction)
*/
enum Direction
{
FORE = 0x00000001,
BACK = 0x00000002,
LEFT = 0x00000004,
RIGHT = 0x00000008
};
typedef struct tagPoint
{
int row, column;
tagPoint ()
{
row = 0;
column = 0;
}
tagPoint(int row, int column)
{
this->row = row;
this->column = column;
}
} Point;
typedef struct tagMatrixPos : public tagPoint
{
int wayDirections, wayDirectionsMarked;
tagMatrixPos()
{
wayDirections = 0;
wayDirectionsMarked = 0;
}
} MatrixPos;
//该类代表一个迷宫
class Matrix
{
private:
int rows, columns;
int directions[4];
MatrixPos *pEndPos;
MatrixPos *pEntrance;
std::vector< std::vector<MatrixPos *> > matrixArray;
std::vector< std::vector<char> > matrixMaps;
std::vector<Point> ways;
protected:
MatrixPos * GetFirstPos()
{
return pEntrance;
}
//判断currentPos节点某个方向是否存在邻居节点
bool HasNextPos(Direction direction, MatrixPos *currentPos)
{
if (currentPos == NULL)
return false;
switch (direction)
{
case FORE:
return currentPos->row < rows - 1;
case LEFT:
return currentPos->column < columns - 1;
case RIGHT:
return currentPos->column > 0;
case BACK:
return currentPos->row > 0;
}
}
//获取currentPos某个方向的邻居节点
MatrixPos *GetPos(Direction direction, MatrixPos *currentPos)
{
if (!HasNextPos(direction, currentPos))
return NULL;
switch (direction)
{
case FORE:
return matrixArray[currentPos->row + 1][currentPos->column];
case LEFT:
return matrixArray[currentPos->row][currentPos->column + 1];
case RIGHT:
return matrixArray[currentPos->row][currentPos->column - 1];
case BACK:
return currentPos->row == 0 ? NULL : matrixArray[currentPos->row - 1][currentPos->column];
}
}
void SetPosition(Direction direction, MatrixPos *pos)
{
pos->wayDirections = pos->wayDirections | (int)direction;
}
//标记节点的某个方向已经走过
void MarkPosition(Direction direction, MatrixPos *pos)
{
pos->wayDirectionsMarked = pos->wayDirectionsMarked | (int)direction;
}
//测试节点的某个方向是否可以通过
bool TestDirection(Direction direction, MatrixPos *pos)
{
if ((pos->wayDirections & direction) != direction)
return false;
return (pos->wayDirectionsMarked & direction) != direction;
}
//从某个节点开始寻径
bool WalkFromPos(MatrixPos *pos)
{
bool hasWay = false;
if (pos == NULL)
return false;
//到达y方向的边界则结束
if (pos->row == rows - 1) {
pEndPos = pos;
return true;
}
//从当前点向前、左、右、后依次测试
for (int i = 0; i < 4; i++) {
if (TestDirection((Direction)directions[i], pos)) {
MatrixPos *pNextPos = GetPos((Direction)directions[i], pos);
MarkPosition((Direction)directions[i], pos);
if (WalkFromPos(pNextPos)) {
hasWay = true;
ways.push_back(Point(pNextPos->row, pNextPos->column));
}
}
}
return hasWay;
}
public:
Matrix()
{
pEntrance = NULL;
pEndPos = NULL;
rows = columns = 0;
directions[0] = FORE;
directions[1] = LEFT;
directions[2] = RIGHT;
directions[3] = BACK;
}
~Matrix()
{
for (int i = 0; i < matrixArray.size(); i++) {
for (int j = 0; j < matrixArray.size(); j++)
delete matrixArray[i][j];
}
matrixArray.clear();
}
bool ReadMatrix(const char* pszFile, int rows, int columns)
{
char pos;
MatrixPos *pCurrent = NULL;
MatrixPos *pRight = NULL;
MatrixPos *pPrev = NULL;
ifstream fin(pszFile);
if (!fin.is_open())
return false;
this->rows = rows;
this->columns = columns;
for (int i = 0; i < rows; i++) {
matrixArray.push_back(std::vector<MatrixPos *>());
matrixMaps.push_back(std::vector<char>());
for (int j = 0; j < columns; j++) {
fin >> pos;
pCurrent = new MatrixPos();
pCurrent->row = i;
pCurrent->column = j;
matrixArray[i].push_back(pCurrent);
matrixMaps[i].push_back(pos);
pRight = GetPos(RIGHT, pCurrent);
pPrev = GetPos(BACK, pCurrent);
//设置其左、后节点的路径
if (pos == '.') {
if (pRight != NULL)
SetPosition(LEFT, pRight);
if (pPrev != NULL)
SetPosition(FORE, pPrev);
if (i == 0)
pEntrance = pCurrent;
}
if (pRight != NULL && matrixMaps[i][j-1] == '.')
SetPosition(RIGHT, pCurrent);
if (pPrev != NULL && matrixMaps[i-1][j] == '.')
SetPosition(BACK, pCurrent);
}
}
fin.close();
return true;
}
//寻找路径
bool Walk()
{
MatrixPos *pCurrentPos = GetFirstPos();
return WalkFromPos(pCurrentPos);
}
//打印路径
void PrintWay()
{
printf ("[%d,%d] - > ", pEntrance->row + 1, pEntrance->column + 1);
for (int i = ways.size() - 1 ; i >= 0 ; i--) {
printf ("[%d,%d] -> ", ways[i].row + 1, ways[i].column + 1);
}
printf ("[%d,%d]", pEndPos->row + 1, pEndPos->column + 1);
}
void PrintMatrix()
{
for (int i = 0; i < rows; i++) {
cout << endl;
for (int j = 0; j < columns; i++) {
cout << matrixMaps[i][j] << endl;
}
}
}
};
int main(int argc, char* argv[])
{
Matrix matrix;
if (!matrix.ReadMatrix("c:\\mg.txt", 16, 16))
printf("read matrix failed");
if (matrix.Walk())
{
printf("Find a way :\n");
matrix.PrintWay();
}
else
printf("no way found");
printf("\npress any key to exit");
getchar();
return 0;
}

複製代碼

不好意思，刚发现论坛将[ i ] 转换成斜体了，所以代码中[ i ] 都没有了。先已更正

[ 本帖最後由 freewave 於 2008-11-11 21:26 編輯 ]

Rank: 1

8^#

發表於 2008-11-9 21:45 | 只看該作者

周末出去玩了 :)
上面我刚写了个例子，是利用递归寻找路径，例如上面16*16的迷宫的路径输出如下（这个路径不是最短路径，需要再加以计算才能得到，抱歉我没有做...）：
[row,column]->[row,column]->....->[row,column] 代表各个点之间的走动

[1,2] - > [2,2] -> [3,2] -> [4,2] -> [4,3] -> [4,4] -> [4,3] -> [4,2] -> [3,2] -
> [2,2] -> [2,3] -> [2,4] -> [2,5] -> [2,6] -> [2,7] -> [2,8] -> [2,9] -> [3,9]
-> [4,9] -> [4,8] -> [5,8] -> [6,8] -> [7,8] -> [7,9] -> [7,10] -> [8,10] -> [9,
10] -> [9,9] -> [10,9] -> [11,9] -> [11,10] -> [11,11] -> [12,11] -> [13,11] ->
[14,11] -> [15,11] -> [14,11] -> [13,11] -> [12,11] -> [11,11] -> [11,12] -> [11
,13] -> [11,14] -> [11,13] -> [11,12] -> [11,11] -> [11,10] -> [11,9] -> [10,9]
-> [9,9] -> [9,10] -> [8,10] -> [7,10] -> [7,9] -> [7,8] -> [7,7] -> [8,7] -> [8
,6] -> [9,6] -> [10,6] -> [11,6] -> [11,5] -> [12,5] -> [13,5] -> [14,5] -> [14,
6] -> [14,7] -> [13,7] -> [13,8] -> [13,9] -> [14,9] -> [15,9] -> [16,9]