用c++写爬蜂房问题

"爬蜂房问题"通常是指在计算机科学中的一种经典动态规划问题，它模拟了蜜蜂沿着蜂巢的格子结构移动的过程。这个任务常常用于教学动态规划算法，尤其是用于求解最短路径问题。

在 C++ 中编写爬蜂房问题的解决方案，你可以采用二维数组来表示蜂巢，其中每个元素代表一个格子，值可能是0（空）、1（墙壁）或者某个正整数（当前的最小步数）。基本步骤如下：

1. 定义一个二维动态规划数组 `dp`，初始化所有边界为无穷大（通常设为 INT_MAX），将起点的步数设为0。
2. 使用两层循环遍历蜂巢，对于每一个格子 `(i, j)`：
- 如果该格子是墙壁（即 dp[i][j] == 1），则跳过；
- 否则，检查四个相邻的格子 `(i+1, j)`, `(i-1, j)`, `(i, j+1)`, 和 `(i, j-1)`，如果它们没有墙壁并且步数加一后的总步数小于当前记录的步数，更新 dp[i][j] 为那个更小的步数。
3. 最终，dp[目的地的行][目的地的列] 就是到达目的地所需的最小步数。

#include <iostream>
using namespace std;

int minSteps(int grid[][GRID_SIZE], int m, int n, int startX, int startY, int endX, int endY) {
    int dp[m][n];
    // 初始化边界
    for (int i = 0; i < m; ++i)
        dp[i][0] = dp[i][n - 1] = INT_MAX;
    for (int j = 0; j < n; ++j)
        dp[0][j] = dp[m - 1][j] = INT_MAX;
    
    if (grid[startX][startY] != 0 || startX < 0 || startY < 0 || startX >= m || startY >= n)
        return -1;

    dp[startX][startY] = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] != 1) { // 非墙壁
                if (i + 1 < m && grid[i + 1][j] != 1)
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
                if (i - 1 >= 0 && grid[i - 1][j] != 1)
                    dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + 1);
                if (j + 1 < n && grid[i][j + 1] != 1)
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
                if (j - 1 >= 0 && grid[i][j - 1] != 1)
                    dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + 1);
            }
        }
    }

    return dp[endX][endY] == INT_MAX ? -1 : dp[endX][endY];
}

// 示例用法
int main() {
    int grid[GRID_SIZE][GRID_SIZE] = {...}; // 蜂巢网格数据
    int start = ...;
    int end = ...;
    cout << "Minimum steps: " << minSteps(grid, rows, cols, start, start, end, end) << endl;
    return 0;
}