房间是N行N列的矩阵,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代表箱子要被推去的位置,4代表搬运工的起始位置,求最后搬运工推箱子的步数。

  问题实质就是五个状态：箱子的位置（bx，by），人的位置（px，py），推箱子的步数。然后用广搜去一一搜索。

#include <iostream>#include <queue>#include <cstring>using namespace std;struct Node{    int px;      //人的x坐标    int py;      //人的y坐标    int bx;      //箱子的x坐标    int by;      //箱子的y坐标    int step;    //箱子被推动的步数};void readData();//读取矩阵void bfs();//广搜int m[10][10];//矩阵bool flag[10][10][10][10];//标记数组，标记每个状态箱子和人的坐标int a[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};//四个方向的移动坐标int n;//矩阵的大小int ex,ey;//箱子终点坐标int bx,by;//箱子起点坐标int sx,sy;//人的起点坐标Node current,next;void readData(){    cin >> n;    for(int i = 0; i < n; i++)    {        for(int j = 0; j < n; j++)        {            cin >> m[i][j];        }    }    for(int i = 0; i < n; i++)    {        for(int j = 0; j < n; j++)        {            if(m[i][j] == 2){//箱子的起始位置				bx = i;				by = j;				m[i][j] = 0;            }            if(m[i][j] == 3){//箱子应该被推到的位置				ex = i;				ey = j;				m[i][j] = 0;            }            if(m[i][j] == 4){//人的起始位置				sx = i;				sy = j;				m[i][j] = 0;            }        }    }}void bfs(){	queue<Node> Q;//队列	memset(flag,false,sizeof(flag));	flag[sx][sy][bx][by]=true;	current.px = sx;	current.py = sy;	current.step = 0;	current.bx = bx;	current.by = by;	Q.push(current);	while(!Q.empty()){		current = Q.front();		Q.pop();		if(current.bx == ex&¤t.by == ey){//箱子到达最终位置			cout << current.step << endl;			return;		}		for(int i = 0;i < 4;i++){//四个方向			next.px = current.px + a[i][0];			next.py = current.py + a[i][1];			next.step = current.step;			//判断当前状态有没有越界			if(next.px >= 0&&next.py >= 0&&next.px < n&& next.py < n&&m[next.px][next.py] != 1){					//下一步人推动了箱子				if(current.bx == next.px&¤t.by == next.py){					int c = next.px + a[i][0];					int d = next.py + a[i][1];			        //判断推动箱子后有没有越界					if(c >= 0&&d >= 0&&d < n&&c < n&&m[c][d] != 1&&flag[next.px][next.py][c][d] == false){						next.bx = c;						next.by = d;						next.step++;						flag[next.px][next.py][next.bx][next.by] = true;						Q.push(next);					}				}				//人没有推动箱子				else{					next.bx = current.bx;					next.by = current.by;					if(flag[next.px][next.py][next.bx][next.by] == false){						flag[next.px][next.py][next.bx][next.by] = true;						Q.push(next);					}				}			}		}	}	cout << "NO PATH!" << endl;}int main(){	readData();	bfs();    return 0;}