一个走迷宫的小程序(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