//本程序取自王曉東編著“算法分析與設計”第 211 頁，例
//分支限界法解布線問題
//
   class WireRouter
   {
     private static class Position
       {
         private int row;               //方格所在的行
         private int col;               //方格所在的列
         
         Position(int rr,int cc)
           {
             row=rr;
             col=cc;
           } 
       private static int [][] grid;     //方格陣列
       private static int size;          //方格陣列大小
       private static int pathLen;       //最短路線長度
       private static ArrayQueue q;      //擴展結點隊列
       private static Position start,    //起點
                               finish;   //終點
       private static Position [] path;  //最短路
      
       private static void inputData()
          {
            MyInputStream keyboard=new MyInputStream();
            System.out.println("Enter grid size");
            size=keyboard.readInteger();
            System.out.println("Enter the start position");
            start=new Position(keyboard.readInteger(),keyboard.readInteger());
            System.out.println("Enter the finish position");
            finish=new Position(keyboard.readInteger(),keyboard.readInteger());
            grid=new int[size+2][size+2];
            System.out.println("Enter the wiring grid in row-major order");
            for(int i=1;i<=size;i++)
              for(int j=1;j<=size;j++)
                grid[i][j]=keyboard.readInteger();
          }
       private static boolean findPath()
          { //計算從起始位置start到目標位置finish的最短布線路徑
            //找到最短布線路徑則返回true ，否則返回false 
            if((start.row==finish.row)&&(start.col==finish.col))
              {//start==finish
                 pathLen=0;
                 return true;
              }
            //初始化相對位移
            Position [] offset=new Position[4];
            offset[0]=new Position(0,1);        //  右
            offset[1]=new Position(1,0);        //  下
            offset[2]=new Position(0,-1);        // 左 
            offset[3]=new Position(-1,0);        // 上

            //設置方格陣列“圍墻”
            for(int i=0;i<=size+1;i++)
              {
               grid[0][i]=grid[size+1][i]=1;     //  頂部和底部 
               grid[i][0]=grid[i][size+1]=1;     //  左翼和右翼
              }    
            Position here=new Position(start.row,start.col);
            grid[start.row][start.col]=2;         // 起始位置的距離
            int numOfNbrs=4;                      // 相鄰方格數
            //標記可達方格位置
            ArrayQueue q=new ArrayQueue();
            Position nbr=new Position(0,0);
            do
              {//標記可達相鄰方格
                for(int i=0; i<numOfNbrs;i++)
                 {
                   nbr.row=here.row+offset[i].row;
                   nbr.col=here.col+offset[i].col;
                   if(grid[nbr.row][nbr.col]==0)
                     {//該方格未標記
                       grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
                        if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成
                        q.put(new Position(nbr.row,nbr.col));
                     }
                  }
                //是否到達目標位置finish?
                if((nbr.row==finish.row)&&(nbr.col==finish.col))break;  //完成
                //活結點隊列是否為非空
                if(q.isEmpty())return false;                   // 無解
                here=(Position)q.remove();                      // 取下一個擴展結點
              }while(true);
            //構造最短布線路徑
            pathLen=grid[finish.row][finish.col]-2;
        System.out.println("最短線路長度  "+pathLen);
            path=new Position[pathLen];
            //  從目標位置finish開始向起始位置回溯
            here=finish;
            for(int j=pathLen-1;j>=0;j--)
              {
                path[j]=here;
                // 找前趨位置
                for(int i=0;i<numOfNbrs;i++)
                  {
                    nbr.row=here.row+offset[i].row;
                    nbr.col=here.col+offset[i].col;
                    if(grid[nbr.row][nbr.col]==j+2)break;
                  }
                here=new Position(nbr.row,nbr.col);//向前移動
              }
            return  true;
          }
        }
  }
 public class Fac6_4
    {
     public static void main(String args[])
       {
         WireRouter abc=new WireRouter();
        // int size1=7;
        // int [][] grid1=new int[size][size];
       //  grid1={{0,0,1,0,0,0,0},{0,0,1,1,0,0,0},{0,0,0,0,1,0,0},{0,0,0,1,1,0,0},
         //       {1,0,0,0,1,0,0},{1,1,1,0,0,0,0},{1,1,1,0,0,0,0}};
         
       }
    }