0元购怎么在网站做,山西做网站哪个好,至设计网站,360推广联盟题干#xff1a;
推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙…题干
推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动. 现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格. Input
输入数据的第一行是一个整数T(1T20),代表测试数据的数量.然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2M,N7),代表房间的大小,然后是一个M行N列的矩阵,代表房间的布局,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代表箱子要被推去的位置,4代表搬运工的起始位置.
Output
对于每组测试数据,输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置,如果不能推到指定位置则输出-1.
Sample Input
1
5 5
0 3 0 0 0
1 0 1 4 0
0 0 1 0 0
1 0 2 0 0
0 0 0 0 0
Sample Output
4
解题报告 很久之前的一道bfs。参照了网上的思路叫他双bfs。就是同时进行两个bfs。记录状态(结构体)和标记状态(bool的数组)的时候也是用四维数组记录。 先让人动如果人刚好走到箱子的位置那么箱子再动这样正好可以控制那个条件箱子必须沿着人动的方向移动。
AC代码
#includebits/stdc.husing namespace std;int maze[9][9],vis[9][9][9][9],n,m;
int nx[4][2] {1,0,0,-1,-1,0,0,1};struct node {int x,y,bx,by,step;bool friend operator (const node a, const node b) {return a.stepb.step;}
} st;
int bfs() {int tx,ty,tbx,tby;node now,next;priority_queuenode q;q.push(st);while(!q.empty()) {nowq.top();if(maze[now.bx][now.by]3) return now.step;for(int i0; i4; i) {txnow.xnx[i][0];tynow.ynx[i][1];if(tx0txnty0tymmaze[tx][ty]!1) {next.xtx;next.yty;next.bxnow.bx;next.bynow.by;next.stepnow.step;if(txnow.bxtynow.by) {tbxtxnx[i][0];tbytynx[i][1];if(tbx0tbxntby0tbymmaze[tbx][tby]!1) {next.bxtbx;next.bytby;next.step;if(vis[tx][ty][next.bx][next.by]0) {vis[tx][ty][next.bx][next.by]1;q.push(next);}}} else if(vis[tx][ty][next.bx][next.by]0) {vis[tx][ty][next.bx][next.by]1;q.push(next);}}}q.pop();}return -1;
}int main() {int t;scanf(%d,t);while(t--) {scanf(%d%d,n,m);memset(vis,0,sizeof(vis));for(int i0; in; i) {for(int j0; jm; j) {scanf(%d,maze[i][j]);if(maze[i][j]4) {st.xi;st.yj;maze[i][j]0;}if(maze[i][j]2) {st.bxi;st.byj;maze[i][j]0;}}}st.step0;vis[st.x][st.y][st.bx][st.by]1;printf(%d\n,bfs());}return 0;
}
