回溯法求迷宫问题
求解思路
1.初始化迷宫：定义一个二维数组表示迷宫，并设定起点和终点。
2.定义回溯函数：通过递归方式探索每一条路径，更新当前路径和步数。
3.剪枝策略：在每一步判断是否需要继续深入（如步数是否已超过最短路径）。
4.输出结果：记录并输出最短路径的长度。
回溯法的基本思想
回溯法通过构建搜索树来逐步尝试所有可能的路径。对于迷宫问题，主要步骤如下：
1.从起点开始，尝试向四个方向（下、左、右、上）移动。
2.如果移动到的新位置是可通行的，则继续进行移动。
3.在每次移动后，检查是否到达终点。
4.若当前位置不再有可移动路径，则回退到上一步，尝试其他方向（即“回溯”）。
5.使用剪枝策略避免不必要的计算，例如：
6.标记已访问的节点，防止重复访问。
7.检查当前路径长度是否已经超过已知的最短路径长度。
代码如下
#include<bits/stdc++.h>
using namespace std;int minSteps = INT_MAX;
int sx,sy,ex,ey;
int n,m;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
int visited[110][110];
char mig[110][110];//迷宫 void backtrack(int x, int y, int steps) {if (x == ex && y == ey) {if (steps < minSteps) {minSteps = steps;}return;}if (steps >= minSteps) return;for (int i = 0; i < 4; ++i) {int newX = x + dx[i];int newY = y + dy[i];if(mig[newX][newY] == '#'){visited[newX][newY] = 1;}if (newX >= 1 && newX <= n && newY >= 1 && newY <= m && mig[newX][newY] == '.') {visited[newX][newY] = 1;backtrack(newX, newY, steps + 1);visited[newX][newY] = 0;}}
}int main() {cin>>n>>m;for(int i = 1; i <= n; i++){scanf("%s", mig[i]+1);}cin>>sx>>sy>>ex>>ey;visited[sx][sy] = 1;backtrack(sx, sy, 0);if (minSteps < INT_MAX) {cout << "最小步数: " << minSteps << endl;} else {cout << "无解" << endl;}return 0;
}
