推箱子c++代码

以下是一个简单的 C++ 实现推箱子游戏的代码，其中用数字表示地图和物品：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 10;

int n, m;
int sx, sy; // 起点坐标
int ex, ey; // 终点坐标
int mp[MAXN][MAXN]; // 地图
int vis[MAXN][MAXN]; // 记录点是否访问过
vector<pair<int, int>> boxs; // 记录箱子位置

bool dfs(int x, int y) {
    if (x == ex && y == ey) return true; // 到达终点
    if (mp[x][y] == 1 || vis[x][y]) return false; // 障碍或已访问过
    vis[x][y] = 1; // 标记为已访问
    for (int i = 0; i < boxs.size(); ++i) {
        int bx = boxs[i].first, by = boxs[i].second;
        if (bx == x && by == y) { // 当前位置有箱子
            int nx = bx + (bx - x), ny = by + (by - y);
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 超出边界
            if (mp[nx][ny] == 1 || vis[nx][ny]) continue; // 障碍或已访问过
            boxs[i].first = nx, boxs[i].second = ny; // 移动箱子
            bool flag = dfs(x, y); // 从新位置开始搜索
            boxs[i].first = bx, boxs[i].second = by; // 恢复箱子位置
            if (flag) return true; // 可以到达终点
            else continue; // 不可到达终点，继续搜索下一个箱子
        }
    }
    if (x + 1 < n && !vis[x+1][y]) { // 向下搜索
        if (dfs(x+1, y)) return true;
    }
    if (x - 1 >= 0 && !vis[x-1][y]) { // 向上搜索
        if (dfs(x-1, y)) return true;
    }
    if (y + 1 < m && !vis[x][y+1]) { // 向右搜索
        if (dfs(x, y+1)) return true;
    }
    if (y - 1 >= 0 && !vis[x][y-1]) { // 向左搜索
        if (dfs(x, y-1)) return true;
    }
    return false; // 无法到达终点
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> mp[i][j];
            if (mp[i][j] == 2) boxs.push_back(make_pair(i, j)); // 记录箱子位置
            else if (mp[i][j] == 3) sx = i, sy = j; // 记录起点坐标
            else if (mp[i][j] == 4) ex = i, ey = j; // 记录终点坐标
        }
    }
    if (dfs(sx, sy)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

该算法使用 DFS（深度优先搜索）实现，对于每个箱子位置，向四个方向搜索箱子可移动的位置，然后以新位置为起点继续搜索，直到找到终点或无法继续搜索为止。