题解：P8628 [蓝桥杯 2015 国 AC] 穿越雷区

题解：P8628 [蓝桥杯 2015 国 AC] 穿越雷区

题目传送门

题目链接

一、题目描述

X星的坦克需要从A区移动到B区，地图由n×n的方阵组成，包含A、B、+、-四种区域。坦克必须交替穿越正负能量区（即不能连续通过两个+或两个-区域），求从A到B的最短路径步数。

二、题目分析

这是一个典型的图论问题，需要在网格地图上寻找满足特定条件的最短路径。关键在于：

1. 移动限制：只能水平或垂直移动
2. 交替规则：不能连续通过相同符号的区域
3. 起点A和终点B都是中性区域

三、解题思路

使用深度优先搜索(DFS)遍历所有可能的路径：

1. 从起点A出发，标记已访问
2. 每次移动检查是否满足交替条件（当前区域符号与前一个不同）
3. 到达B点时记录最小步数
4. 使用剪枝优化：当当前步数已超过已知最小步数时提前终止

四、算法讲解

DFS算法结合剪枝：

1. 状态表示：当前位置(x,y)、当前步数cnt、上一个区域符号ch
2. 终止条件：到达B点
3. 剪枝优化：当cnt ≥ ans时直接返回
4. 回溯：每次尝试后恢复访问状态

五、代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, ans = 1e9;
char g[N][N];
bool st[N][N];
int a1, b1, c2, d2;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// DFS函数：x,y当前位置，cnt当前步数，ch前一个区域的符号
void dfs(int x, int y, int cnt, char ch)
{
    // 剪枝：当前路径已不可能是最优解
    if (cnt >= ans) return ;
    // 终止条件：到达B点
    if (x == c2 && y == d2)
    {
        ans = min(ans, cnt);
        return ;
    }
    // 尝试四个方向
    for (int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        // 边界检查
        if (a < 1 || b < 1 || a > n || b > n) continue;
        // 访问检查
        if (st[a][b]) continue;
        // 交替规则检查
        if (g[a][b] == ch) continue;
        
        st[a][b] = 1; // 标记访问
        dfs(a, b, cnt + 1, g[a][b]);
        st[a][b] = 0; // 回溯
    }
}

void solve()
{
    cin >> n;
    // 读入地图并记录A、B坐标
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            cin >> g[i][j];
            if (g[i][j] == 'A')
                a1 = i, b1 = j;
            if (g[i][j] == 'B')
                c2 = i, d2 = j;
        }
    // 从A点开始搜索，初始步数为0，前一个符号为'A'（中性）
    dfs(a1, b1, 0, 'A');
    // 输出结果
    if (ans != 1e9)
        cout << ans << "\n";
    else 
        cout << -1 << "\n";
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

六、重点细节

1. 初始状态处理：A点作为起点，符号为’A’，不会与任何实际符号冲突
2. 边界检查：确保移动不超出地图范围
3. 符号交替规则：通过比较当前区域符号与前一个符号来保证交替
4. 访问标记：防止重复访问同一区域
5. 回溯处理：搜索完成后恢复访问状态，以便其他路径可以访问该点

七、复杂度分析

• 时间复杂度：最坏情况下为O(4^n)，但由于剪枝优化，实际运行效率较高
• 空间复杂度：O(n²)，主要用于存储地图和访问状态

八、总结

本题通过DFS+剪枝的方式解决了最短路径问题，关键在于：

1. 正确处理交替规则的限制条件
2. 使用剪枝优化提高搜索效率
3. 注意回溯时状态的恢复
   对于n<100的规模，这种解法在合理时间内可以得到答案。