New Page 1

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

C.第三版

在第二版改进“聪明地”在一定范围内直接查找“直达”路径基础上，第三版解决了“原地”打转的问题：

如果起始点不在迷宫边缘，而是在中央某处，就会有可能出现这种情况：围着某一点转圈。怎么解决呢？我在每次开始走下一步之前看从前的路径里是否重复了，如果是就说明我在打转了，这时候，我为了能够跳出圈子，改变前进方向：方向加一。

1。所谓路径重复，有两点必须一样，首先，前进方向一致，其次，位置一致。因为虽然走过同一点并不说明重复，只有在同一点的前进方向也一样才是重复转圈。所以，分两步，先找同样方向，再找同样位置。

    bool foundRepeat(Pos * pos)
    {
    	bool checkNext(int &start, Direction dir);
    	bool samePos(int);

    	int start = counter -1;
    	int first = start;

    	while (checkNext(start, trace[counter - 1]))   //这里是在找所有方向与当前（counter - 1才是当前位置）。一致的点
    	{
    		if (samePos(start))     //检验是否为同一点
    		{
    			return true;
    		}
    	}
    	return false;

    }

    //同一个点当然是转了一圈又恢复原状。

    bool samePos(int start)
    {
    	int row=0, col=0;
    	for (int i= start; i<counter - 1; i++)  //circle before current cursor "counter" (counter - 1才是当前位置）
    	{
    		switch(trace[i])
    		{
    		case Right:
    			col++;
    			break;
    		case Left:
    			col--;
    			break;
    		case Up:
    			row--;
    			break;
    		case Down:
    			row++;
    			break;
    		}
    	}
    	return (row==0&&col==0);
    }

    2。如果发现转圈就想办法跳出来。

    (direction==Down)?(direction = Right):(direction=(Direction)(direction +1));

    在进行通常的方向确定之前，作方向的调整才是正确的步骤，这个次序决不能错，这也是害我debug好辛苦的一点。

    	if (foundRepeat(pos))  //if circling, then think to make a change
    		{
    			(direction==Down)?(direction = Right):(direction=(Direction)(direction +1));

    		}
    		direction = findDirection(pos, direction);

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

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

    	if (checkGoal(pos))
    		return true;
    	else
    	{
    		if (foundRepeat(pos))  //if circling, then think to make a change
    		{
    			(direction==Down)?(direction = Right):(direction=(Direction)(direction +1));

    		}
    		direction = findDirection(pos, direction);

    		progress(pos, direction);
    		return mazeTraverse(pos, direction);
    	}
    }

    3。同时为使起始点处在中央需要把初始化函数作修改。

    先找结束的点，因为出口可能只有一个啊，那就是结束的点，起始点在最后确认。

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

    	bool endFound= 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]&&isGate(row, col))
    			{
    				if (!endFound)
    				{
    					End.row = row;
    					End.col = col;
    					endFound = true;
    				}
    				else
    				{
    					Start.row = row;
    					Start.col = col;
    				}

    			}
    		}
    	}

    	if (!endFound)     //如果连一个出口都没有是不对的。
    	{
    		cout<<"but there is no exit!";
    		exit(1);
    	}

    	if (randomStart)     //看起始点的位置旗标决定在中间随机确定。
    	{
    		do
    		{
    			Start.row = rand() % Dimension;
    			Start.col = rand() % Dimension;
    		}
    		while (Maze[Start.row][Start.col]);
    	}
    }

    以下为第三版全部代码。

    #include <iostream>
    #include <ctime>
    #include <cstdlib>

    using namespace std;

    const int Dimension = 10;
    const int Chance =4;
    const int SearchRange = 4;
    const int CheckLength = 10;
    enum Direction
    { Right, Up, Left, Down };

    struct Pos
    {
    	int row;
    	int col;
    };

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

    Pos Start;
    Pos End;
    Direction findDirection(Pos* pos, Direction direction);

    bool foundRepeat(Pos * pos);

    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, bool randomStart= false);

    int main()
    {
    	Direction  dir;

    	srand(time(0));
    	initialize("data.txt", true);
    	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;

    	dir = initializeDir();

    	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 randomStart)
    {
    	bool isGate(int, int);

    	bool endFound= 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]&&isGate(row, col))
    			{
    				if (!endFound)
    				{
    					End.row = row;
    					End.col = col;
    					endFound = true;
    				}
    				else
    				{
    					Start.row = row;
    					Start.col = col;
    				}

    			}
    		}
    	}

    	if (!endFound)
    	{
    		cout<<"but there is no exit!";
    		exit(1);
    	}

    	if (randomStart)
    	{
    		do
    		{
    			Start.row = rand() % Dimension;
    			Start.col = rand() % Dimension;
    		}
    		while (Maze[Start.row][Start.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)
    {
    	bool shortCut(Pos* pos);
    	void goShortCut(Pos* pos);

    	if (shortCut(pos))
    	{
    		goShortCut(pos);
    		return true;
    	}
    	return (pos->row == End.row && pos->col == End.col);
    }

    void goShortCut(Pos* pos)
    {
    	int row, col, i=0;
    	int rowOffSet=0, colOffSet = 0;
    	Direction dir;

    	row = pos->row;
    	col = pos->col;
    	while (i < SearchRange)
    	{
    		//you have to go step by step, otherwise diagonal is illegal
    		if (row != End.row)
    		{
    			rowOffSet = (pos->row > End.row ?-1: 1);  //-1means up
    			row += rowOffSet;
    			if (rowOffSet !=0)
    			{
    				dir = (Direction)(rowOffSet < 0?1:3);
    				writeRecord(dir);
    			}
    		}
    		if (col != End.col)
    		{
    			colOffSet = (pos->col >End.col? -1: 1); //-1 means left
    			col += colOffSet;
    			if (colOffSet!=0)
    			{
    				dir = (Direction)(colOffSet < 0? 2:0);
    				writeRecord(dir);
    			}
    		}
    		i++;
    	}
    }

    bool shortCut(Pos* pos)
    {
    	int row, col, i=0;

    	if (abs(pos->row - End.row)<SearchRange&&abs(pos->col - End.col)< SearchRange)
    	{

    		row = pos->row;
    		col = pos->col;
    		while (i<SearchRange)
    		{
    			if (row != End.row)
    			{
    				row += (pos->row > End.row ?-1: 1);
    				if (Maze[row][col])
    					return false;
    			}
    			if (col != End.col)
    			{
    				col += (pos->col >End.col? -1: 1);
    				if (Maze[row][col])
    					return false;
    			}
    			i++;
    		}
    		return true;
    	}
    	return false;
    }

    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;
    	return Right;
    }

    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);
    }

    bool checkNext(int &start, Direction dir)
    {
    	while ((counter - start)< CheckLength&&start>1)
    	{
    		start--;
    		if (trace[start]== dir)
    			return true;
    	}
    	return false;
    }

    bool samePos(int start)
    {
    	int row=0, col=0;
    	for (int i= start; i<counter - 1; i++)  //circle before current cursor "counter"
    	{
    		switch(trace[i])
    		{
    		case Right:
    			col++;
    			break;
    		case Left:
    			col--;
    			break;
    		case Up:
    			row--;
    			break;
    		case Down:
    			row++;
    			break;
    		}
    	}
    	return (row==0&&col==0);
    }

    bool foundRepeat(Pos * pos)
    {
    	bool checkNext(int &start, Direction dir);
    	bool samePos(int);

    	int start = counter -1;
    	int first = start;

    	while (checkNext(start, trace[counter - 1]))   //same pos and same direction means repeat
    	{
    		if (samePos(start))
    		{
    			return true;
    		}
    	}
    	return false;

    }

    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
    	{
    		if (foundRepeat(pos))  //if circling, then think to make a change
    		{
    			(direction==Down)?(direction = Right):(direction=(Direction)(direction +1));

    		}
    		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":"  ");
    		}
    	}
    }

    从下图可以看到，实际在第二个Down之后就应该跳出重复圈子，也就是第二个Left应该改变，可是凑巧的是那一点正好“碰壁”，只能在一次

    Left,可是下一点就会发现Left重复了要改变，于是，在Left之后改了。真好，改了就好！

以下为输入文件样子：

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