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