【数据结构】之迷宫问题

所谓迷宫，就是在一个矩阵中，从开始位置有一条通路可以走到最末尾的位置

先画一个迷宫，格式为txt，和编译的文件夹放在一起

在迷宫中，0表示可以走通的路，而1则表示不可走通的墙

首先定义一个结构体，用来存放行和列

struct Pos { size_t row; size_t col; };接下来从文件中获得迷宫 的矩阵

void GetMaze(int *maze, size_t N) { FILE *fp = fopen("MazeMap.txt", "r"); if (fp == NULL) { throw invalid_argument("Read maze filed"); } for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < N;) { char ch = fgetc(fp); if (ch == '0' || ch == '1') { maze[i*N + j] = ch - '0'; } else if (ch == EOF) { throw invalid_argument("Maze Error"); } } } }然后就要判断迷宫中的每一个坐标的路是否为通路

bool CheckIsAccess(int* maze, size_t N, Pos next) { if (maze[next.row*N + next.col] == 0) { return true; } return false; }

接下俩对于路径的求解的算法有两种方法，递归和非递归

非递归求解：

bool GetMazePath(int *maze, size_t n, Pos entry, stack<Pos>&path) { maze[entry.row*N + entry.col] = 2; Pos cur, next; cur = entry; path.push(entry); while (!path.empty()) { cur = path.top(); if (cur.row == N - 1) { return true; } next = cur; next.row += 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; next.row -= 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; next.col += 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; next.col -= 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; path.pop(); } return false; }

用递归的方法：

void GetMazePath_R(int *maze, size_t N,Pos entry, stack<Pos>&path,stack<Pos>&shortpath) { if (entry.row == N - 1) { if (path.size() < shortpath.size() || shortpath.size() == 0) { shortpath = path; } path.pop(); return; } Pos cur, next; cur = entry; next = cur; next.row += 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1; GetMazePath_R(maze, N, next, path, shortpath); } next = cur; next.row -= 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1; GetMazePath_R((int*)maze, N, next,path, shortpath); } next.col += 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1; GetMazePath_R((int*)maze, N, next, path, shortpath); } next.col -= 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + next.col] + 1; GetMazePath_R((int*)maze, N, next, path, shortpath); } path.pop(); }

其中的-=1和+=1是表示在一个位置处有四个方向，通过行和列的+1和-1来表示这四个方向。

下面就是完整的代码：

#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; #include<stack> const int N = 10; struct Pos { size_t row; size_t col; }; void PrintMaze(int *maze, size_t N) { for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < N; ++j) { cout << maze[i*N + j] << " "; } cout << endl; } cout << endl; } bool CheckIsAccess(int *maze, size_t N, Pos next) { if (maze[next.row*N + next.col] == 0) { return true; } return false; } bool CheckIsAccess(int *maze, size_t N, Pos next, Pos cur) { if (next.row < 0 || next.row >= N || next.col < 0 || next.col >= N) { return false; } if (maze[next.row*N + next.col] == 0) { return true; } return(maze[next.row*N + next.col]>(maze[cur.row*N + next.col] + 1)); } void GetMaze(int *maze, size_t N) { FILE *fp = fopen("MazeMap.txt", "r"); if (fp == NULL) { throw invalid_argument("Read maze filed"); } for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < N;) { char ch = fgetc(fp); if (ch == '0' || ch == '1') { maze[i*N + j] = ch - '0'; ++j; } else if (ch == EOF) { throw invalid_argument("Maze Error"); } } } } bool GetMazePath(int *maze, size_t n, Pos entry, stack<Pos>&path) { maze[entry.row*N + entry.col] = 2; Pos cur, next; cur = entry; path.push(entry); while (!path.empty()) { cur = path.top(); if (cur.row == N - 1) { return true; } next = cur; next.row += 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; next.row -= 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; next.col += 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; next.col -= 1; if (CheckIsAccess((int*)maze, N, next) == true) { path.push(next); maze[next.row*N + next.col] = 2; continue; } next = cur; path.pop(); } return false; } void GetMazePath_R(int *maze, size_t N,Pos entry, stack<Pos>&path,stack<Pos>&shortpath) { if (entry.row == N - 1) { if (path.size() < shortpath.size() || shortpath.size() == 0) { shortpath = path; } path.pop(); return; } Pos cur, next; cur = entry; next = cur; next.row += 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1; GetMazePath_R(maze, N, next, path, shortpath); } next = cur; next.row -= 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1; GetMazePath_R((int*)maze, N, next,path, shortpath); } next.col += 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1; GetMazePath_R((int*)maze, N, next, path, shortpath); } next.col -= 1; if (CheckIsAccess((int*)maze, N, next, cur) == true) { path.push(next); maze[next.row*N + next.col] = maze[cur.row*N + next.col] + 1; GetMazePath_R((int*)maze, N, next, path, shortpath); } path.pop(); } void ReMaze(int* maze) { for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < N; ++j) { if (maze[i*N + j] != 1) { maze[i*N + j] = 0; } } } } stack<Pos>MinPath() { int maze[N][N] = { 0 }; int curmaze[N][N] = { 0 }; GetMaze((int*)maze, N); stack<Pos>path, MinPath, empty; while (GetMazePath((int*)maze, N, { 0, 0 }, path)) { if (path.size() < MinPath.size()||MinPath.size() == 0) { MinPath = path; } ReMaze((int*)maze); maze[path.top().row][path.top().col] = 1; path = empty; } return MinPath; } void Test() { try { int maze[N][N] = { 0 }; int curmaze[N][N] = { 0 }; GetMaze((int*)maze, N); stack<Pos>path, shortpath; path.push({ 0, 0 }); GetMazePath_R((int*)maze, N, { 0, 0 }, path, shortpath); cout << shortpath.size() << endl; } catch (exception &e) { cout << e.what() << endl; } } int main() { Test(); system("pause"); return 0; }