New Page 1

    一个走迷宫的小程序(A)

    A.第一版

    这个小程序是最初的版本，计划最近增强功能以便对于程序能够根据记忆跳出死循环的小圈子。

    1。 迷宫的输入，一开始时是靠简单的算法自动生成，后来发现不理想就用文件输入。

    2。 程序写得不很高明，用了太多全局变量，因为我讨厌船参数（改函数改得太多了，参数多，改起来麻烦）。

    3。 每到一格，先向右转，按逆时针测试能否前进。（也就是说前进方向的右手变为第一优先方向。）

    4。 目前设定两个出口，起始位置为一个出口，走到另一个出口为成功，并打印路径。

    #include <iostream>

    using namespace std;

    const int Dimension = 10;
    const int Chance =4;

    enum Direction
    { Right, Up, Left, Down };

    struct Pos
    {
    	int row;
    	int col;
    };

    char * str[]={"Right", "Up", "Left", "Down"};

    Pos Start;
    Pos End;

    void writeRecord(Direction direction);

    bool Maze[Dimension][Dimension] = {false};

    void display();

    Direction initializeDir();

    Direction trace[100];
    int counter =0;

    bool mazeTraverse(Pos* pos, Direction& direction);

    void progress(Pos* pos, Direction& direction);

    bool checkGoal(Pos* pos);

    void initialize(char * fileName);

    int main()
    {
    	initialize("data.txt");
    	display();
    	cout<<"\nStart gate is["<<Start.row<<"]["<<Start.col<<"]"<<endl;
    	cout<<"End gate is["<<End.row<<"]["<<End.col<<"]"<<endl;
    	Pos* pos = new Pos;
    	pos->row = Start.row;
    	pos->col = Start.col;
    	Direction  dir;
    	dir = initializeDir();
    	progress(pos, dir);
    	if (mazeTraverse(pos, dir))
    	{
    		for (int i=0; i<counter;i++)
    			cout<<str[trace[i]]<<(((i+1)%6==0)?"\n":"\t");
    		cout<<endl;
    	}
    	else
    		cout<<"\nfail\n";

    	return 0;
    }

    bool isGate(int row, int col)
    {
    	return (row==0||row==Dimension -1||col==0||col==Dimension -1);
    }

    void initialize(char * fileName)
    {
    	bool isGate(int, int);

    	bool startFound= false;
    	FILE *stream;
    	stream = fopen(fileName, "r");
    	if (!stream)
    		cout<<"wrong!\n";

    	for (int row=0; row< Dimension; row++)
    	{
    		for (int col=0; col< Dimension; col ++)
    		{
    			char ch;
    			ch = fgetc(stream);
    			while (ch == 10 || ch == 32)
    				ch = fgetc(stream);
    			Maze[row][col] = (bool)(atoi(&ch));
    			if (!Maze[row][col])
    			{
    				if (!startFound)
    				{
    					if (isGate(row, col))
    					{
    						Start.row = row;
    						Start.col = col;
    						startFound = true;
    					}
    				}
    				else
    				if (isGate(row, col))
    				{
    					End.row = row;
    					End.col = col;
    				}
    			}
    		}
    	}
    }

    Direction nextDirection(Direction direction)
    {
    	if (direction==Down)
    		return Right;
    	else
    		return (Direction)(direction + 1);
    }

    bool testPos(int row, int col)
    {
    	if (row>Dimension-1||row<0||col>Dimension-1||col<0)
    		return false;
    	return  !Maze[row][col];
    }

    bool checkGoal(Pos* pos)
    {
    	return (pos->row == End.row && pos->col == End.col);
    }

    Direction initializeDir()
    {
    	if (Start.col == 0)
    		return Right;
    	if (Start.col == Dimension -1)
    		return Left;
    	if (Start.row == 0)
    		return Down;
    	if (Start.row == Dimension - 1)
    		return Up;
    }

    bool testDirection(Pos* pos, Direction direction)
    {
    	bool testPos(int row, int col);

    	int row= pos->row, col = pos->col;
    	switch(direction)
    	{
    	case Right:
    		col = pos->col + 1;
    		break;
    	case Up:
    		row = pos->row - 1;
    		break;
    	case Left:
    		col = pos->col - 1;
    		break;
    	case Down:
    		row = pos->row + 1;
    		break;
    	}
    	return testPos(row, col);
    }

    Direction prevDirection(Direction direction)
    {
    	if (direction == Right)
    		return Down;
    	return (Direction)(direction - 1);
    }

    Direction findDirection(Pos* pos, Direction direction)
    {
    	bool testDirection(Pos* pos, Direction direction);
    	Direction nextDirection(Direction direction);
    	Direction prevDirection(Direction direction);

    	Direction newDir;
    	newDir = prevDirection(direction);
    	while (!testDirection(pos, newDir))
    	{
    		newDir = nextDirection(newDir);
    	}
    	return newDir;
    }

    bool mazeTraverse(Pos* pos, Direction& direction)
    {

    	void progress(Pos* pos, Direction& direction);

    	if (checkGoal(pos))
    		return true;
    	else
    	{
    		direction = findDirection(pos, direction);
    		progress(pos, direction);
    		return mazeTraverse(pos, direction);
    	}
    }

    void progress(Pos* pos, Direction& direction)
    {
    	switch(direction)
    	{
    	case Right:
    		pos->col += 1;
    		break;
    	case Up:
    		pos->row += -1;
    		break;
    	case Left:
    		pos->col += -1;
    		break;
    	case Down:
    		pos->row += 1;
    		break;
    	}
    	writeRecord(direction);
    }

    void writeRecord(Direction direction)
    {
    	trace[counter] = direction;
    	counter++;
    }

    void display()
    {
    	for (int row = 0; row< Dimension; row++)
    	{
    		for (int col=0; col < Dimension; col++)
    		{
    			cout<<Maze[row][col]<<((col==Dimension-1)?"\n":"  ");
    		}
    	}
    }

    以下为运行结果：（从最左面的入口出发，到达右面出口，进入过一个死胡同并退出。）

以下为输入文件样子：

1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
0 0 0 1 0 1 1 1 1 1
1 1 0 1 0 1 1 0 0 1
1 1 0 0 0 1 0 0 0 1
1 1 1 0 1 1 0 1 0 1
1 0 0 0 0 0 0 1 0 0
1 0 1 0 0 0 1 0 0 1
1 0 1 0 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1