|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
/*
|
|
|
一、定义：
|
|
|
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
|
|
|
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就
|
|
|
退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
|
|
|
用回溯法求解问题时常使用递归方法进行试探，或使用栈帮助向前试探和回溯。
|
|
|
|
|
|
二、思路：
|
|
|
1.用一个二维数组表示迷宫：
|
|
|
数组中的值如果是1，则表示该位置是墙壁，不能通行；
|
|
|
如果等于0，表示该位置是通路；
|
|
|
用一个标记数组，标记该位置是否被访问过；
|
|
|
2.迷宫前进的方向：要定义一个结构体存储方向
|
|
|
可能有8个方向：东，东南，南，西南，西，西北，北，东北
|
|
|
3.给一个入口和出口的坐标，从入口入手：
|
|
|
循环入口的8个方向，如果位置通，则递归该位置，一直递归下去，直到到达出口或者所有方向的路不通回溯；
|
|
|
*/
|
|
|
|
|
|
// 默认迷宫的行数和列数
|
|
|
const int XLEN = 14, YLEN = 17;
|
|
|
|
|
|
int m, p; // 出口坐标
|
|
|
int maze[XLEN + 2][YLEN + 2]; // 迷宫数组
|
|
|
int mark[XLEN + 2][YLEN + 2]; // 访问标记数组
|
|
|
|
|
|
// 结果体，代表一个二维数组的元素,a和b是x,y方向的偏移
|
|
|
struct Offsets {
|
|
|
int a, b;
|
|
|
};
|
|
|
|
|
|
// 因为不需要输出方向，所以把方向去掉
|
|
|
Offsets direction[8] =
|
|
|
{{-1, 0},
|
|
|
{-1, 1},
|
|
|
{0, 1},
|
|
|
{1, 1},
|
|
|
{1, 0},
|
|
|
{1, -1},
|
|
|
{0, -1},
|
|
|
{-1, -1}
|
|
|
};
|
|
|
|
|
|
// 解决迷宫问题的递归算法
|
|
|
bool seekPath(int x, int y) {
|
|
|
// 从迷宫某一位置[i][j]开始，寻找出口[m][p]的一条路径,如果找到，则函数返回true
|
|
|
int i, g, h; // g, h记录位置信息
|
|
|
|
|
|
if (x == m && y == p) // m和p是出口坐标
|
|
|
return true;
|
|
|
|
|
|
// 循环遍历(x, y)的8个方向
|
|
|
for (i = 0; i < 8; i++) {
|
|
|
g = x + direction[i].a;
|
|
|
h = y + direction[i].b;
|
|
|
|
|
|
// 找下一位置寻找通向出口的路径
|
|
|
if (maze[g][h] == 0 && mark[g][h] == 0) { // 如果通且未被访问过
|
|
|
mark[g][h] = 1; // 标记为已访问过
|
|
|
if (seekPath(g, h)) { // 递归试探
|
|
|
cout << "(" << g << ", " << h << ")，"; // 逆向输出路径坐标
|
|
|
return true;
|
|
|
}
|
|
|
}
|
|
|
// 回溯，换一个方向再试探通向出口的路径
|
|
|
}
|
|
|
return false; // 找不到通向出口的路径
|
|
|
}
|
|
|
|
|
|
int main(int argc, const char *argv[]) {
|
|
|
//读取数据文件
|
|
|
freopen("./data.txt", "r", stdin);
|
|
|
int i, j, x, y;
|
|
|
|
|
|
// 输入迷宫数据
|
|
|
for (i = 0; i < XLEN; i++) {
|
|
|
for (j = 0; j < YLEN; j++) {
|
|
|
cin >> maze[i][j];
|
|
|
//初始化标记数组
|
|
|
mark[i][j] = 0;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//输入入口位置坐标
|
|
|
cin >> x >> y;
|
|
|
|
|
|
//输入出口位置坐标
|
|
|
cin >> m >> p;
|
|
|
|
|
|
// 从入口开始
|
|
|
mark[x][y] = 1;
|
|
|
|
|
|
// 调用求解迷宫的递归算法
|
|
|
if (seekPath(x, y)) // 成功
|
|
|
{
|
|
|
cout << "(" << x << ", " << y << ")" << endl;
|
|
|
} else {
|
|
|
cout << "找不到从入口到出口的路径！" << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
