题目描述
推箱子是一款经典游戏。这里我们玩的是一个简单版本,就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请问玩家至少要多少步才能达成目标？
输入
第一行输入两个数字N，M表示地图的大小。其中0
输出
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
样例输入 Copy
6 6
...#..
......
#*##..
..##.#
..X...
.@#...
样例输出 Copy
11
整体分析：
使用C语言编写使用广度优先搜索（BFS）实现推箱子游戏的代码，其主要目的包括：
这段C++代码实现了一个基于广度优先搜索（BFS）算法的迷宫问题求解器，特别适用于解决类似于推箱子这样的谜题。下面是对代码的详细解析：
头文件和命名空间：
using namespace std; 来避免在标准库类型和函数前加 std::。状态四维数组 state：
结构体 q：
px, py 和箱子的位置 bx, by。移动方向数组 moves：
地图数组 map：
边界检查函数 bound：
true。广度优先搜索算法 bfs：
主函数 main：
n 和 m。bfs 函数进行搜索，并将结果输出。程序结束：
system("pause") 暂停程序，等待用户操作。代码逻辑分析：
潜在问题：
scanf 读取字符串时，没有指定字符串的最大长度，可能导致缓冲区溢出。改进建议：
std::cin 和 std::getline 替代 scanf 来读取地图布局，以提高代码的安全性和可读性。std::vector 或 std::array 替代原始数组，以提高代码的灵活性和健壮性。**广度优先搜索（Breadth-First Search, BFS）**是一种遍历或搜索树或图的算法，它从一个节点开始，逐层遍历节点，即首先访问起始节点的所有邻接节点，然后访问邻接节点的邻接节点，依此类推。这种搜索方法常用于寻找最短路径或仅仅是对图的遍历。
使用一个队列来存储待处理的状态。
从初始状态开始，不断探索所有可能的移动，直到找到目标状态或所有状态都被访问过。
如果找到目标状态，返回到达该状态的步数减1；如果无法找到，则返回-1。
BFS是一种简单但强大的算法，适用于多种应用场景，特别是在需要层次遍历或寻找最短路径时。
在C++中，q(int x, int y, int bx, int by) :px(x), py(y), bx(bx), by(by) {} 是一个结构体 q 的构造函数初始化列表。
构造函数：q 是结构体名，q(int x, int y, int bx, int by) 定义了一个构造函数，它接收四个参数：x、y、bx 和 by。
参数意义：
x 和 y 通常表示人（或主角）在网格地图上的坐标。bx 和 by 表示箱子在网格地图上的坐标。初始化列表：:px(x), py(y), bx(bx), by(by) 是一个初始化列表，它用于在创建 q 类型对象时直接初始化其成员变量。
px 和 py 是结构体 q 的成员变量，分别存储人的横纵坐标。bx 和 by 是结构体 q 的成员变量，分别存储箱子的横纵坐标。作用：这个构造函数的作用是创建一个 q 类型的对象，并用传入的参数值初始化该对象的成员变量。这样做的好处是可以直接在创建对象时设置其状态，避免了后续再单独设置成员变量的需要。
使用场景：在这段代码中，构造函数用于初始化表示搜索状态的对象。在广度优先搜索（BFS）算法中，每个状态（人和箱子的位置）都需要被明确记录和处理。使用构造函数可以方便地将这些状态封装为对象。
代码示例：
struct q {
int px, py, bx, by;
q(int x, int y, int bx, int by) :px(x), py(y), bx(bx), by(by) {} // 构造函数
};
在 BFS 中使用：
q temp(chx, chy, cbx, cby); // 创建一个状态对象，初始为人在 (chx, chy)，箱子在 (cbx, cby)
q(int x, int y, int bx, int by) :px(x), py(y), bx(bx), by(by) {} 是一个构造函数，通过初始化列表设置结构体 q 的成员变量，使得每个 q 类型的对象都能清晰地表示一个搜索状态。在算法实现中，这种封装和初始化方式有助于代码的清晰性和易管理性。
边界检查，遇到不合理的位置返回真
bool bound(int x, int y)//边界检查，遇到不合理的位置返回真
{
if (x < 0 || y < 0 || x >= n || y >= m || map[x][y] == '#')
return true;
else
return false;
}
广度优先算法
int bfs()
{
state[chx][chy][cbx][cby] = 1;//当前其实状态位置设步数为1
q temp(chx, chy, cbx, cby);
queue<q> que; //状态队列
que.push(temp);//初始状态入栈
while (que.size()) //只要队列不为空就一直寻找
{
temp = que.front();//获取首元素
que.pop();//首元素弹出
if (temp.bx == ex&&temp.by == ey)
return state[temp.px][temp.py][temp.bx][temp.by] - 1;//如果箱子在终点，结束，返回步数
for (int i = 0; i < 4; i++)//四个方向开始搜索了
{
//先更新人的位置
int px = temp.px + moves[i][0];
int py = temp.py + moves[i][1];
if (bound(px, py))
continue;//如果这个位置非法，探寻其它方向
if (px == temp.bx&&py == temp.by)//如果此时人的位置与箱子的位置重合，说明人应当推动了箱子
{
if (bound(temp.bx + moves[i][0], temp.by + moves[i][1]))
continue;//如果箱子移动的位置不合法，则重新探寻其它方向
state[px][py][temp.bx + moves[i][0]][temp.by + moves[i][1]] =
state[temp.px][temp.py][temp.bx][temp.by] + 1;//箱子推动，则人和箱子位置改变，记录新状态
que.push(q(px, py, temp.bx + moves[i][0], temp.by + moves[i][1]));//新状态入栈
}
else//人没有推动箱子
{
if (state[px][py][temp.bx][temp.by])//如果移动后的状态出现过，则重新搜索新方向
continue;
state[px][py][temp.bx][temp.by] = state[temp.px][temp.py][temp.bx][temp.by] + 1;
//没有走过这条路就走着试试
que.push(q(px, py, temp.bx, temp.by));//更新状态
}
}
}
return -1;//如果所有位置都试过了，没有找到，说明不存在
}
#include