求推箱子的最小步数（java)

题目（poj1475)：推箱子，要求箱子移动步骤最小。如图：T为目标地，B为箱子，S为推箱子的人，要求将B推到T，步骤最少。



[输入输出]:




[解题分析]:
题解：双重bfs，先对箱子bfs，然后判断这种bfs是否可达（对人bfs）

下面是AC过的代码：

import java.util.*;
import java.io.*;
 public class Main{
  int r;//地图行数
  int c;//地图列数
  int begx, begy;//箱子开始坐标
  int endx, endy;//目标坐标
  int begsx, begsy;//人开始坐标
  char map[][];//地图
  int[] dx ={-1, 1, 0, 0};//人和箱子都有四个方向可移动
  int[] dy ={0, 0, 1, -1};
  char[] P ={'N', 'S', 'E', 'W'};//表示箱子向某个方向移动
  char[] M ={'n', 's', 'e', 'w'};//表示人向某个方向移动
  Node f=new Node(0,0,0,0,"");
  Node g=new Node(0,0,0,0,"");
  node1 F=new node1(0,0,"");
  node1 G=new node1(0,0,"");
  int mark[][];//标志数组，表示地图上某一位置mark[i][j]是否访问过。
  
 
   public Main(char[][] map,int r,int c,int begx,int begy,int endx,int endy,int begsx,int begsy){
     this.map=map;
     this.r=r;
     this.c=c;
     this.begx=begx;
     this.begy=begy;
     this.endx=endx;
     this.endy=endy;
     this.begsx=begsx;
     this.begsy=begsy;
      mark=new int[r][c];   
     }
 
  
 public boolean  ok(int x,int  y) {
    if (x >= 0 && x < r && y >= 0 && y < c) return true;
    return false;
  }

  public boolean SToB(int bx,int by,int ex, int ey) {//人到箱子BFS
 
    int[][] Mark1= new int[r][c];   //标志数组，表示地图上某一位置Mark1[i][j]是否访问过。
    
    Queue<node1> P = new LinkedList<node1>();  
    Mark1[bx][by] = 1;
    Mark1[f.bx][f.by] = 1;
    F.x = bx; F.y = by;
    F.ans = "";
    if (bx == ex && by == ey) return true;//到达目标
    P.offer(new node1(F.x,F.y,F.ans));
    while (!P.isEmpty()) {
        F = P.poll();
        for (int i = 0; i < 4; ++i) {//向四个方向扩展
            G.x = F.x + dx[i];
            G.y = F.y + dy[i];
            if (!ok(G.x, G.y) || map[G.x][G.y] == '#') continue;
            if (Mark1[G.x][G.y]==0) {//此点没有访问过
              
                Mark1[G.x][G.y] = 1;//标记为已访问
                G.ans = F.ans + M[i];
                if (G.x == ex && G.y == ey) {
                    F = G;
                    return true;
                }
                P.add(new node1(G.x,G.y,G.ans));
                
            }
        }
    }
    return false;
 }
 
 public boolean  bfs() {//箱子向目标bfs
    Queue<Node> Q = new LinkedList<Node>();  
    f.bx = begx; f.by = begy;//f:人与箱子所在的位置
    f.px = begsx; f.py = begsy;
    f.ans = "";
    mark[begx][begy] = 1;
    Q.offer(new Node(f.bx,f.by,f.px,f.py,f.ans));
    while (!Q.isEmpty()) {
      f = Q.poll();//出队列
      for (int i = 0; i < 4; ++i) {//检查f的所有邻接点，向四个方向扩展
         int newx = f.bx + dx[i];
         int  newy = f.by + dy[i];//箱子前一位置
         int  tx = f.bx - dx[i];
         int  ty = f.by - dy[i];//箱子后一位置
         if (!ok(newx, newy) || map[newx][newy] == '#' || !ok(tx, ty) 
		      || map[tx][ty] == '#' || mark[newx][newy]==1) continue;
           if (SToB(f.px, f.py, tx, ty)) {//检查人能否来
             g.bx = newx; g.by = newy;
             g.px = f.bx; g.py = f.by;
             g.ans = f.ans + F.ans + P[i];
             if (g.bx == endx && g.by == endy) 
             {
               return true;
              }
              mark[newx][newy] = 1;
              Q.add(new Node(g.bx,g.by,g.px,g.py,g.ans));    
            }
      }
   }
    return false;
 }

 
public static void main(String args[]) {   
    Scanner in=new Scanner(System.in);
    int r=0;
    int c=0;
    String s="";
    int begx=0;
    int begy=0;
    int endx=0;
    int endy=0;
    int begsx=0;
    int begsy=0;
    char[][] map=null;
    int t=1;
    while(in.hasNext()){
      r=in.nextInt();
      c=in.nextInt();
      if(r==0&&c==0) break;
      map=new char[r][c];
      for(int i = 0; i <r; i++){
         s=in.next();
         for(int j=0;j< c;j++){
            map[i][j]=s.charAt(j);
           if (map[i][j] == 'B') { begx = i; begy = j;}//箱子开始坐标
           if (map[i][j] == 'T') { endx = i; endy = j;}//目标坐标
           if (map[i][j] == 'S')  { begsx = i;begsy = j;}//人开始坐标
         }

      }
      Main ma=new Main(map,r,c,begx,begy,endx,endy,begsx,begsy);
       if (ma.bfs()) {
              System.out.println("Maze #"+t++);
              System.out.println(ma.g.ans);
              System.out.println();
        }
        else{ 
          System.out.println("Maze #"+t++);
          System.out.println("Impossible."); 
           System.out.println();
   
        }
  
   }
 }

  }

class node1{
    int x;
    int y;
    String ans;
   public node1(int x,int y,String ans){
    this.x=x;
    this.y=y;
    this.ans=ans;
 }
}

 class Node{
    int bx;
    int by;
    int px;
    int py;
    String ans;
   public Node(int bx,int by,int px,int py,String ans) {
    this.bx=bx;
    this.by=by;
    this.px=px;
    this.py=py;
    this.ans=ans;
 } 
}

评论

1 楼 hlstudio 2014-05-06  

好久没见到sokuban了，这有个java版的，带源码，可以参考下 http://sourceforge.net/projects/mywork/