面试题：C++ 深度优先搜索优化与剪枝策略

Question

在一个复杂的迷宫求解问题中，迷宫由一个二维字符数组表示，'#' 表示墙壁，' ' 表示可通行路径，'S' 为起点，'E' 为终点。要求使用C++ 的深度优先搜索算法来找到从起点到终点的最短路径。同时，在搜索过程中需要运用有效的剪枝策略来优化搜索效率，例如记录已经访问过的无效路径。请详细描述你的剪枝策略，并给出完整的C++ 代码实现。迷宫数组定义如下： ```cpp char maze[100][100]; ```

Answer 1

剪枝策略

1. 访问标记：使用一个与迷宫大小相同的二维布尔数组 visited 记录每个位置是否已经被访问过。如果一个位置已经被访问过，再次到达该位置时就无需重复搜索，直接跳过，这可以避免在已经探索过的路径上浪费时间。
2. 边界检查：在访问每个位置之前，先检查该位置是否在迷宫的边界内。如果越界，直接返回，不进行进一步探索。
3. 墙壁检查：如果当前位置是墙壁（即 maze[i][j] == '#'），直接返回，不进行探索。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 100;
char maze[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int minPathLength = INT_MAX;
vector<pair<int, int>> path;
vector<pair<int, int>> shortestPath;

void dfs(int x, int y, int length) {
    if (x < 0 || x >= MAXN || y < 0 || y >= MAXN || maze[x][y] == '#' || visited[x][y]) {
        return;
    }
    visited[x][y] = true;
    path.emplace_back(x, y);
    if (maze[x][y] == 'E') {
        if (length < minPathLength) {
            minPathLength = length;
            shortestPath = path;
        }
    } else {
        for (int i = 0; i < 4; ++i) {
            dfs(x + dx[i], y + dy[i], length + 1);
        }
    }
    path.pop_back();
    visited[x][y] = false;
}

int main() {
    int n, m;
    cout << "请输入迷宫的行数和列数: ";
    cin >> n >> m;
    cout << "请输入迷宫: " << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> maze[i][j];
        }
    }
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (maze[i][j] == 'S') {
                dfs(i, j, 0);
            }
        }
    }
    if (minPathLength != INT_MAX) {
        cout << "最短路径长度为: " << minPathLength << endl;
        cout << "最短路径为: " << endl;
        for (const auto& p : shortestPath) {
            cout << "(" << p.first << ", " << p.second << ") ";
        }
        cout << endl;
    } else {
        cout << "没有找到从起点到终点的路径" << endl;
    }
    return 0;
}