题目描述

在一个 H 行 W 列的网格地图中，高桥要从起点 (A, B) 移动到终点 (C, D)。地图由道路（’.’）和墙壁（’#’）组成。起点和终点保证是道路。
高桥可以执行两种操作：
1. 移动: 移动到相邻（上、下、左、右）的、在网格内且是道路的单元格。
2. 前踢: 选择一个方向（上、下、左、右），并向该方向执行前踢。当前位置在该方向上最多 2 步距离内的所有单元格，如果是墙壁，则会变成道路。如果目标单元格在网格外，则无效。

目标是找到从起点到达终点所需的最少前踢次数。移动本身不计入次数。

样例

输入:
10 10
..........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
.##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...
1 1 7 1

输出:
1

说明：从 (1,1) 出发，可以通过道路移动到 (7,4)。在 (7,4) 向左进行一次前踢，(7,3) 和 (7,2) 的墙壁变成道路。之后可以通过道路移动到终点 (7,1)。总共需要 1 次前踢。

算法 (0-1 BFS)

$O(H \times W)$

思路分析

这个问题可以看作是一个图上的最短路径问题。网格中的每个单元格 (i, j) 可以看作图中的一个节点。我们需要找到从起点 (A, B) 到终点 (C, D) 的路径，使得路径上 “前踢” 操作的次数最少。

我们观察两种操作的 “代价”：
1. 移动: 在相邻的道路格之间移动。这个操作不增加前踢次数，可以认为代价是 0。
2. 前踢: 执行一次前踢。这个操作本身算作 1 次前踢，代价是 1。前踢之后，被破坏的墙壁变成了道路，后续在这些新道路上的移动代价仍然是 0。

由于存在两种代价（0 和 1），这个问题非常适合使用 0-1 宽度优先搜索 (0-1 BFS) 来解决。0-1 BFS 本质上是 Dijkstra 算法在边权只有 0 和 1 情况下的优化，使用双端队列 (deque) 来维护待访问的节点。

状态定义:
我们可以用 (d, r, c) 来表示一个状态，其中 d 是到达单元格 (r, c) 所需的最小前踢次数。

距离数组:
我们使用一个二维数组 dis[H][W] 来存储到达每个单元格 (r, c) 所需的最小前踢次数。初始化 dis 数组的所有值为 -1（或一个表示无穷大的值），表示尚未访问。

0-1 BFS 过程:
1. 初始化双端队列 q，并将起始状态 {0, A, B}（0 次前踢，在起点 (A, B)）放入队列。注意，坐标需要转换为 0-based，即 (A-1, B-1)。
2. 初始化 dis[A-1][B-1] = 0。
3. 当队列 q 不为空时，执行以下操作：
* 从 队首 取出状态 (d, x, y)。队首的元素总是当前具有最小前踢次数的状态。
* 如果 dis[x][y] 已经被更新过（即 dis[x][y] != -1），说明我们已经找到了到达 (x, y) 的一条路径，且其前踢次数小于或等于 d。由于我们总是从队首取出最小代价的状态，所以当前路径不会更优，直接跳过此状态 (continue)。
* 将 dis[x][y] 的值最终确定为 d。
* 探索邻居: 从当前状态 (d, x, y) 出发，考虑所有可能的下一步：
* 代价为 0 的转移 (普通移动): 检查 (x, y) 的上、下、左、右四个相邻单元格 (nx, ny)。如果 (nx, ny) 在网格内且是道路 (S[nx][ny] == '.')，那么从 (x, y) 移动到 (nx, ny) 不需要额外的踢墙次数，总代价仍然是 d。如果通过这条路径到达 (nx, ny) 比之前记录的路径更好（即 dis[nx][ny] == -1 或 dis[nx][ny] > d），则将新状态 {d, nx, ny} 加入到 队首。
* 代价为 1 的转移 (需要前踢): 考虑从 (x, y) 进行一次前踢后可能到达的单元格。一次前踢会影响目标方向上最多 2 步距离的墙壁。这意味着，如果我们决定在 (x, y) 附近执行一次前踢（总代价增加到 d + 1），我们之后就可以移动到那些原本是墙壁或者距离稍远的单元格。
代码中的实现方式是：考虑从 (x, y) 出发，可以到达其周围 5x5 区域内的所有单元格 (nx, ny)，付出的代价是 d + 1。为什么是 5x5 区域？因为一次前踢最多破坏 2 格墙，之后可能还需要最多 2 步的普通移动才能到达目标格子。这个 5x5 的范围 (x+i, y+j) 其中 -2 <= i, j <= 2 足够覆盖所有 “执行一次踢墙 + 最多两步移动” 所能到达的格子。对于这个范围内的每个合法单元格 (nx, ny)，如果通过这条需要踢墙的路径（总代价 d + 1）到达 (nx, ny) 比之前记录的路径更好（即 dis[nx][ny] == -1 或 dis[nx][ny] > d + 1），则将新状态 {d + 1, nx, ny} 加入到 队尾。

1. 持续这个过程，直到队列为空。
2. 最终 dis[C-1][D-1] 的值就是从起点 (A, B) 到终点 (C, D) 所需的最少前踢次数。如果 dis[C-1][D-1] 仍然是 -1，则表示无法到达终点（虽然题目保证起点终点是路，但不保证一定联通）。

代码逻辑解读:
提供的 C++ 代码实现了 0-1 BFS 的思想。
deque<array<int, 3>> q;: 双端队列存储状态 {kicks, row, col}。
vector dis(H, vector<int>(W, -1));: 存储最小前踢次数。
q.push_back({0, A, B});: 将起点加入队列（代码里写 push_back，但因为队列初始为空，效果等同 push_front）。
while (!q.empty()): BFS 主循环。
auto [d, x, y] = q.front(); q.pop_front();: 取出队首状态。
if (dis[x][y] != -1) continue;: 如果已处理过，跳过。
dis[x][y] = d;: 确定 (x, y) 的最小前踢次数。
移动 (Cost 0): for (int k = 0; k < 4; k++) ... if (S[nx][ny] == '.') ... q.push_front({d, nx, ny}); 这部分处理移动到相邻道路格的情况，将状态 {d, nx, ny} 加入队首。代码中增加了 if (dis[nx][ny] == -1 || dis[nx][ny] > d) 的判断，确保只有在找到更优路径时才加入队列，这是标准的优化。
* 踢墙 (Cost 1): for (int i = -2; i <= 2; i++) for (int j = -2; j <= 2; j++) ... q.push_back({d + 1, nx, ny}); 这部分处理需要一次踢墙的情况。它遍历 (x, y) 周围 5x5 区域内的所有格子 (nx, ny)，并将 {d + 1, nx, ny} 加入队尾。同样，代码中增加了 if (dis[nx][ny] == -1 || dis[nx][ny] > d + 1) 的判断。

这种将 “踢墙+移动” 建模为直接到达 5x5 区域内任意格子（代价+1）的方式，结合 0-1 BFS 优先处理代价 0 的移动，可以正确找到最少踢墙次数。

时间复杂度

每个单元格 (x, y) 最多会被加入队列两次（一次代价为 d，一次代价为 d+1）。处理每个单元格时，我们需要检查 4 个相邻单元格（代价 0）和最多 25 个 5x5 区域内的单元格（代价 1）。这些操作都是常数时间。因此，总的时间复杂度是 O(H * W)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名

// 定义四个方向的偏移量：下, 右, 上, 左
constexpr int dx[] = {1, 0, -1, 0};
constexpr int dy[] = {0, 1, 0, -1};

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int H, W; // 地图高度 H, 宽度 W
    cin >> H >> W;

    vector<string> S(H); // 存储地图的 H 行字符串
    for (int i = 0; i < H; i++) {
        cin >> S[i]; // 读入每一行地图
    }

    int A, B, C, D; // 起点 (A, B), 终点 (C, D) (1-based)
    cin >> A >> B >> C >> D;
    // 转换为 0-based 坐标
    A--;
    B--;
    C--;
    D--;

    // dis[i][j] 存储到达单元格 (i, j) 所需的最小前踢次数
    // 初始化为 -1 表示未到达
    vector dis(H, vector<int>(W, -1));
    // 创建双端队列，用于 0-1 BFS
    // 存储 {前踢次数, 行坐标, 列坐标}
    deque<array<int, 3>> q;
    // 将起点加入队列，初始前踢次数为 0
    q.push_back({0, A, B}); // 或者 q.push_front({0, A, B}); 效果一样

    // 0-1 BFS 主循环
    while (!q.empty()) {
        // 从队首取出当前最优状态 (最小前踢次数)
        auto [d, x, y] = q.front();
        q.pop_front();

        // 如果单元格 (x, y) 已经被访问过 (且有更优或相等的路径)
        // dis[x][y] != -1 意味着之前已经找到了到达 (x, y) 的路径
        // 由于我们总是从队首取出 d 最小的状态，所以第一次访问 (x,y) 时 d 一定是最小的
        if (dis[x][y] != -1) {
            continue; // 跳过，不再处理
        }
        // 确定到达 (x, y) 的最小前踢次数为 d
        dis[x][y] = d;

        // --- 探索代价为 0 的转移 (普通移动) ---
        for (int k = 0; k < 4; k++) { // 遍历四个方向
            int nx = x + dx[k]; // 计算相邻单元格的行坐标
            int ny = y + dy[k]; // 计算相邻单元格的列坐标

            // 检查是否越界
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) {
                continue;
            }

            // 如果相邻单元格是道路 ('.')
            if (S[nx][ny] == '.') {
                // 如果 (nx, ny) 尚未访问，或者当前路径代价 d 更小
                if (dis[nx][ny] == -1 || dis[nx][ny] > d) {
                    // 将状态 {d, nx, ny} 加入队首 (代价为 0 的转移)
                    q.push_front({d, nx, ny});
                }
            }
        }

        // --- 探索代价为 1 的转移 (需要前踢) ---
        // 遍历以 (x, y) 为中心的 5x5 区域 (-2 <= i, j <= 2)
        for (int i = -2; i <= 2; i++) {
             for (int j = -2; j <= 2; j++) {
                 // if (i == 0 && j == 0) continue; // 可以跳过中心点，但代码没跳，不影响正确性

                 int nx = x + i; // 计算目标单元格的行坐标
                 int ny = y + j; // 计算目标单元格的列坐标

                 // 检查是否越界
                 if (nx < 0 || nx >= H || ny < 0 || ny >= W) {
                     continue;
                 }

                 // 如果 (nx, ny) 尚未访问，或者当前路径代价 d + 1 更小
                 if (dis[nx][ny] == -1 || dis[nx][ny] > d + 1) {
                     // 将状态 {d + 1, nx, ny} 加入队尾 (代价为 1 的转移)
                     q.push_back({d + 1, nx, ny});
                 }
             }
        }
    }

    // 输出到达终点 (C, D) 所需的最小前踢次数
    cout << dis[C][D] << "\n";

    return 0; // 程序正常结束
}