前言：
我的地图文件（MazeMap.txt）如下：
计算
安全
数据库
网络和加速
企业服务
size:(a,a)
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 1 1
1 1 0 1 1 1 1 0 1 1
1 1 0 1 1 1 1 0 1 1
1 1 0 1 1 1 1 0 1 1下面的pos类用来保存某个位置的坐标
GetMaze函数用来判断地图格式的合法性，若合法则读取地图内容，并将内容存入参数arr所指向的内存中。
struct pos
{
pos(int row = 0, int col = 0)
:_row(row)
,_col(col)
{}
int _row;
int _col;
};
void GetMaze(int *&arr, int &sz, int &row, int &col)
{
FILE *fout = fopen("MazeMap.txt", "r");
assert(fout);
char *title = new char[40];
title = fgets(title, 7, fout);
if (strcmp(title, "size:("))
{
cout << "地图文件错误！" << endl;
throw 1;
}
row = fgetc(fout) - 87;
title = fgets(title, 2, fout);
if (strcmp(title, ","))
{
cout << "地图文件错误！" << endl;
throw 1;
}
col = fgetc(fout) - 87;
arr = new int[row * col];
sz = row * col;
title = fgets(title, 2, fout);
for (int i = 0; i < sz; i)
{
char ch = fgetc(fout);
if (ch != ' ' && ch != '\n' && ch != '\0')
{
*(arr + i) = ch - '0';
i++;
}
}
}一、找到出口
bool MazePath(int *arr, int n, const pos &entry, stack<pos> &path) //假设下边沿为迷宫的出口
{
pos cur = entry;
path.push(cur);
while (!path.empty())
{
*(arr + n * (cur._row)+cur._col) = 2;
if (cur._row == n - 1)
{
return true;
}
//向下
if
((cur._row + 1 < 10) && (*(arr + n * (cur._row + 1) + cur._col) == 0))
{
*(arr + n * (cur._row + 1) + cur._col) = 2;
++cur._row;
path.push(cur);
continue;
}
//向上
if
((cur._row - 1 >= 0) && (*(arr + n * (cur._row - 1) + cur._col) == 0))
{
*(arr + n * (cur._row - 1) + cur._col) = 2;
--cur._row;
path.push(cur);
continue;
}
//向左
if
((cur._col - 1 >= 0) && (*(arr + n * cur._row + cur._col - 1) == 0))
{
*(arr + n * cur._row + cur._col - 1) = 2;
--cur._col;
path.push(cur);
continue;
}
//向右
if ((cur._col + 1 < 10) && (*(arr + n * cur._row + cur._col + 1) == 0))
{
*(arr + n * cur._row + cur._col + 1) = 2;
++cur._col;
path.push(cur);
continue;
}
//走不通
cur._col = path.top()._col;
cur._row = path.top()._row;
path.pop();
}
}二、找到所有出口并得出最短路线（最优解）
template <typename T>
void ClearPath(stack<T> &stack)
{
while (!stack.empty())
{
stack.pop();
}
}
static void SaveBestPath(stack<pos> &path, vector< stack<pos> > path_vec)
{
stack<pos> best_path;
int sz = (path_vec.back()).size();
best_path = path_vec.back();
while (!path_vec.empty())
{
if (sz > (path_vec.front()).size())
{
best_path = path_vec.front();
}
path_vec.pop_back();
}
path = best_path;
}
static struct Exit
{
Exit(int row, int col)
:_row(row)
,_col(col)
{}
int _row;
int _col;
};
//堵住已知的出口 (为了不销毁数据，不使用引用)
static void BlockKnownExit(int *arr, vector< Exit> exit_vec, int n)
{
Exit ext1 = exit_vec.back();
while (!exit_vec.empty())
{
ext1 = exit_vec.back();
*(arr + n * ext1._row + ext1._col) = 3;
exit_vec.pop_back();
}
}
//假设下边沿为迷宫的出口
bool MazePathMin(int *arr, int n, const pos &entry, stack<pos> &path)
{
vector< stack<pos> > path_vec; //用于存放所有的路径
vector< Exit > exit_vec; //用于存储所有出口
pos cur = entry;
path.push(cur);
while (!path.empty() )
{
*(arr + n * (cur._row) + cur._col) = 2;
if (cur._row == n - 1)
{
//找到一个出口
*(arr + n * (cur._row) + cur._col) = 3;
Exit ext_tmp(cur._row, cur._col);
path_vec.push_back(path);
exit_vec.push_back(ext_tmp);
//清空路径，寻找除该出口外的其他出口
ClearPath(path);
GetMaze(arr, n);
BlockKnownExit(arr, exit_vec, n);
cur = entry;
path.push(cur);
}
//向下
if ((cur._row + 1 < 10) && (*(arr + n * (cur._row + 1) + cur._col) == 0))
{
*(arr + n * (cur._row + 1) + cur._col) = 2;
++cur._row;
path.push(cur);
continue;
}
//向上
if ((cur._row - 1 >= 0) && (*(arr + n * (cur._row - 1) + cur._col) == 0))
{
*(arr + n * (cur._row - 1) + cur._col) = 2;
--cur._row;
path.push(cur);
continue;
}
//向左
if ((cur._col - 1 >= 0) && (*(arr + n * cur._row + cur._col - 1) == 0))
{
*(arr + n * cur._row + cur._col - 1) = 2;
--cur._col;
path.push(cur);
continue;
}
//向右
if ((cur._col + 1 < 10) && (*(arr + n * cur._row + cur._col + 1) == 0))
{
*(arr + n * cur._row + cur._col + 1) = 2;
++cur._col;
path.push(cur);
continue;
}
//走不通的时候：
cur._col = path.top()._col;
cur._row = path.top()._row;
path.pop();
}
//path为空
SaveBestPath(path, path_vec); //把最佳的路径保存进path中（仍然倒序）
return (!path.empty());
}三、优化后的算法
四、用递归实现
//待续
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
