wirerouter.java

布线问题算法分析与设计实现程序JAVA版

import java.util.*;
/**
 * 布线问题的分支限界法
 * @author wangwei
 *
 */
  /*
		Scanner in = new Scanner(System.in);
		System.out.print("input the n:");
		n = in.nextInt();
   */
public class WireRouter {
	private static int[][] grid = new int[9][9];        //方格阵列
	//grid[1][3] = grid[2][3] = grid[2][4] =  grid[3][5] = grid[4][4] = grid[4][5] = grid[5][1] = grid[6][1] =  grid[6][2] = grid[6][3] = grid[7][1] =  grid[7][2] = grid[7][3] = 1;
	private static int size = 7;            //方格阵列的大小
	private static int pathLen;          //最短线路长度
	private static ArrayQueue q;        //扩展结点队列
	//private static Position start,finish;   //布线的起点和终点
	private static Position start=new Position(3,2);
	private static Position finish = new Position(4,6);
	private static Position[] path;         //最短路
	//private static int spx;
	//private static int spy;
	//private static int fpx;
	//private static int fpy;
	
	public static void main(String[] args){
		grid[1][3] = grid[2][3] = grid[2][4] =  grid[3][5] = grid[4][4] = grid[4][5] = 
			grid[5][1] = grid[5][5] = grid[6][1] =  grid[6][2] = grid[6][3] = grid[7][1] =  
				grid[7][2] = grid[7][3] = 1;
		//WireRouter.inputDate();
		WireRouter.findPath();
		System.out.print("布线的最短路径是：");
		System.out.println(pathLen);
		for(int i = 0;i < path.length;i++){
			path[i].display();
			System.out.print("-->");
		}
		System.out.print("b(4,6)");
	
	}
	/*如果想动态决定网格，可以用这个函数
	public static void inputDate(){
		Scanner in = new Scanner(System.in);
		System.out.println("请输入方格的大小：");
		size = in.nextInt();
		grid = new int[size+2][size+2];
		System.out.println("请输入要布线的开始点的坐标：");
		spx = in.nextInt();
		spy = in.nextInt();
		start = new Position(spx,spy);
		
		System.out.println("请输入要布线的终点的坐标：");
		fpx = in.nextInt();
		fpy = in.nextInt();
		finish = new Position(fpx,fpy);
		
		System.out.println("Enter teh wiring grid in row-major order");
		for(int i = 1;i <= size;i++)
			for(int j = 1;j <= size;j++)
				grid[i][j] = in.nextInt();
		
	}
	*/
	 //-----------12-20-22:48----------------------
	public static boolean findPath(){
		//若找到start到finish的最短路径，返回true，否则返回false
		if((start.row == finish.row)&&(start.col == finish.col)){
			pathLen = 0;
			return true;
		}
		
		//初始相对位移
		Position[] offset = new Position[4];
		offset[0] = new Position(0,1);    //right
		offset[1] = new Position(1,0);    //down
		offset[2] = new Position(0,-1);   //left
		offset[3] = new Position(-1,0);   //up
		
		//设置方格阵列围墙
		for(int i = 0;i <= size + 1;i++){
			grid[0][i] = grid[size + 1][i] = 1;   //up and down
			grid[i][0] = grid[i][size + 1] = 1;    //left and right
		}
		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;  //have no result
			here = (Position)q.remove();  //get the next extensive node
		}while(true);
		
		//构造最短布线路径
		pathLen = grid[finish.row][finish.col] - 2;
		path = new Position[pathLen];
		//从目标位置finish开始向开始位置回溯
		here = finish;
		for(int j = pathLen - 1;j >= 0;j--){
			path[j] = here;
			//find the forword
			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;
	}
	

}