14 搜索（回溯 / 剪枝）与迷宫类问题

#include <iostream>
using namespace std;
const int N = 20;
int n;
bool used[N];        // used[i]：数字 i 是否已被使用
int a[N];            // a[k]：第 k 个位置填的数

// 回溯求全排列：dfs(k) 表示正在填第 k 个位置
void dfs(int k) {
    if (k == n) {                    // 已填满 -> 输出一个完整解
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {   // 枚举当前位可选的数字
        if (!used[i]) {              // 数字 i 还没用过
            used[i] = true;          // 占用：标记
            a[k] = i;                // 填数
            dfs(k + 1);              // 递归填下一位
            used[i] = false;         // 回溯：撤销标记，供下一分支使用
        }
    }
}
int main() {
    n = 4;
    dfs(0);                          // 输出 1..4 的全排列
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
const int N = 105;
int n, m;
char mp[N][N];       // 地图
bool vis[N][N];      // 访问标记
int dx[4] = {-1, 1, 0, 0};   // 上下左右四个方向
int dy[4] = {0, 0, -1, 1};

// DFS 判断从 (x,y) 能否到达终点 'E'
bool dfs(int x, int y) {
    if (mp[x][y] == 'E') return true;   // 到达终点
    vis[x][y] = true;                   // 标记当前格
    for (int d = 0; d < 4; d++) {       // 枚举四个方向
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 越界跳过
        if (vis[nx][ny] || mp[nx][ny] == '#') continue;        // 已走过或是墙
        if (dfs(nx, ny)) return true;   // 找到路立即返回
    }
    return false;                       // 四条路都走不通
}
int main() {
    n = 3; m = 3;
    string raw[3] = {"S..", "#.#", "..E"};   // S 起点，# 墙，. 空地
    int sx = 0, sy = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            mp[i][j] = raw[i][j];
            if (mp[i][j] == 'S') sx = i, sy = j;   // 记录起点
        }
    }
    cout << (dfs(sx, sy) ? "可达" : "不可达") << endl;
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
using namespace std;
const int N = 105;
int n, m;
char mp[N][N];       // 地图
int step[N][N];      // step[i][j]：从起点到 (i,j) 的最少步数
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
const int INF = 1e9;

// BFS 求最短步数（边权为 1 的网格）
int bfs(int sx, int sy, int ex, int ey) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) step[i][j] = INF;   // 初始全不可达
    queue<pair<int, int>> q;
    q.push({sx, sy});
    step[sx][sy] = 0;                // 起点步数 0
    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();   // C++11 兼容写法
        int x = cur.first, y = cur.second;
        if (x == ex && y == ey) return step[x][y];   // 到终点即最短
        for (int d = 0; d < 4; d++) {   // 向四个方向扩展
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 越界
            if (mp[nx][ny] == '#') continue;   // 墙
            if (step[nx][ny] != INF) continue; // 已访问过（第一次才最短）
            step[nx][ny] = step[x][y] + 1;     // 步数 +1
            q.push({nx, ny});
        }
    }
    return -1;   // 队列空仍未到终点：不可达
}
int main() {
    n = 4; m = 4;
    string raw[4] = {"S..#", "..#.", "....", "#..E"};
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) mp[i][j] = raw[i][j];
    cout << bfs(0, 0, 3, 3) << endl;   // 最短步数
    return 0;
}

// 记忆化搜索：用 memo 记录已算过的子问题，避免重复递归
#include <iostream>
#include <string>
using namespace std;
const int N = 20;
int n, m;
char mp[N][N];
long long memo[N][N];    // memo[x][y]：从 (x,y) 出发的路径数（-1 未算）
bool vis[N][N];          // 是否已计算过

long long dfsPath(int x, int y) {
    if (x == n - 1 && y == m - 1) return 1;      // 到终点：1 条路
    if (x >= n || y >= m) return 0;              // 越界：0 条
    if (mp[x][y] == '#') return 0;               // 墙：0 条
    if (vis[x][y]) return memo[x][y];            // 已记忆：直接返回
    vis[x][y] = true;                            // 标记已算
    // 只能向右、向下走：路径数 = 右 + 下
    memo[x][y] = dfsPath(x + 1, y) + dfsPath(x, y + 1);
    return memo[x][y];
}
int main() {
    n = 3; m = 3;
    string raw[3] = {"...", ".#.", "..."};
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) mp[i][j] = raw[i][j];
    cout << dfsPath(0, 0) << endl;
    return 0;
}