推箱子
推箱子是一個很經典的游戲.今天我們來玩一個簡單版本.在一個M*N的房間里有一個箱子和一個搬運工,搬運工的工作就是把箱子推到指定的位置,注意,搬運工只能推箱子而不能拉箱子,因此如果箱子被推到一個角上(如圖2)那么箱子就不能再被移動了,如果箱子被推到一面墻上,那么箱子只能沿著墻移動.
現在給定房間的結構,箱子的位置,搬運工的位置和箱子要被推去的位置,請你計算出搬運工至少要推動箱子多少格.
Input
輸入數據的第一行是一個整數T(1<=T<=20),代表測試數據的數量.然后是T組測試數據,每組測試數據的第一行是兩個正整數M,N(2<=M,N<=7),代表房間的大小,然后是一個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
思路：把問題拆分
1：如果單看箱子的移動，就是一個bfs求最短。
2：但是這里多了條件就是需要人去推，那么在箱子移動就要記錄小人移動的位置，小人推箱子前的位置和需要在的位置推箱子，要判斷能否到達，這又是一個bfs。要注意小人除了箱子的位置和墻奇特都可以走。要判斷小人是否越界，可走。
3：這里的人和箱子的位置是會變的，然而他們的初始位置是標記其他數字不是0，最好將他的數字改成0，使用參數單獨標記其位置。
4：人的遍歷要記憶一次遍歷，因為我要求的只是到達。但是箱子的遍歷要記錄不是走一次，一個位置可走兩次?？赡芟渥涌ㄔ陂T口推出去，人再內，人在推出去推進來。
5：箱子要用優先隊列優化，標記為推得次數。
代碼如下：

import java.util.ArrayDeque; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner;public class 杭電1254 {static int x1,y1,x2,y2,x3,y3,m,n;//人 箱子 結束點static int x[]= {0,1,0,-1};static int y[]= {1,0,-1,0};static int a[][];//存儲值static boolean jud=false;public static void main(String[] args) {Scanner sc=new Scanner(System.in);int t=sc.nextInt();//測試數據for(int t1=0;t1 q2=new PriorityQueue(comepare);//優先隊列q2.add(new xiang(x2,y2,x1,y1,0));//加入第一個箱子和人的位子while(!q2.isEmpty()){xiang xiang=q2.poll();int x4=xiang.xx;int y4=xiang.yx;//箱子int x5=xiang.xr;int y5=xiang.yr;//renif(x4==x3&&y4==y3){System.out.println(xiang.time);jud=true;break;}else for(int i=0;i<4;i ){if(x4 x[i]>=0&&x4 x[i]=0&&y4 y[i]=0&&x4-x[i]=0&&y4-y[i]2)//允許它來回一次，也就是這個點可以走兩次mark[x4 x[i]][y4 y[i]]=true;}}}}}}if(!jud) {System.out.println(-1);}jud=false; }} public static boolean move(int x11,int y11,int x21,int y21,int x41,int y41 )//起始點，末尾，箱子 {boolean b[][]=new boolean[m][n];Queue q1=new ArrayDeque();b[x11][y11]=true;//起點和箱子當作遍歷過b[x41][y41]=true;q1.add(new zuobiao(x11,y11)); while(!q1.isEmpty()){zuobiao zuo=q1.poll();int x31=zuo.x;int y31=zuo.y;if(x31==x21&&y31==y21){return true;}else for(int i=0;i<4;i ){if(x31 x[i]>=0&&x31 x[i]=0&&y31 y[i]comepare=new Comparator() {public int compare(xiang arg0, xiang arg1) {return(int) (arg0.time-arg1.time);}}; private static class xiang{int xx;int yx;//箱子int xr;int yr;//人int time;public xiang(int xx,int yx,int xr,int yr,int time){this.xx=xx;this.yx=yx;this.xr=xr;this.yr=yr;this.time=time;}} private static class zuobiao {int x;int y;public zuobiao(int x,int y){this.x=x;this.y=y;} } }

總結

以上是生活随笔為你收集整理的杭电1254java实现（双bfs 优先队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。