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