wirerouter.java

用java写的布线问题的界面演示程序

package Buxian;

import java.util.*;

public class WireRouter {
	private static int[][] grid ; // 方格阵列

	private static int size ; // 方格阵列的大小

	private static int pathLen; // 布线线路长度

	private static LinkedList<Position> q; // 扩展结点队列

	private static Position start,finish ;//起点和终点

	private static Position[] path; // 记录布线路径信息
	
//构造函数初始化	
public WireRouter(int size,Position start,Position finish)	{
		 WireRouter.size=size;
	     WireRouter.grid=new int[size+2][size+2];
       
		//设置方格阵列围墙
		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
		}
		
			  
		//随机生成障碍！
		for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
		{
			Random r=new Random();
			if(r.nextDouble()>0.7)
				grid[i+1][j+1]=1;
			else
				grid[i+1][j+1]=0;
		}
		
        //初始化起点和终点状态
		WireRouter.start=start;
		WireRouter.finish=finish;
		grid[start.row][start.col]=2;
		grid[finish.row][finish.col]=0;
		
}

	
//实现从终端输入起点和终点坐标信息!
public static Position input(int size)throws InputMismatchException
  {
	    int spx,spy;
	    boolean b=true;
		Scanner in = new Scanner(System.in);
	 try{
		 spx = in.nextInt();
	 	 spy = in.nextInt();
	 	 if(spx<=size&&spy<=size)
	 	  return  new Position(spx, spy);
	 	 else
	 	 {  do{
	 		 System.out.print("坐标值超出方格范围，请重输：");
	 		 in = new Scanner(System.in);
	 		 spx = in.nextInt();
		 	 spy = in.nextInt();
		 	 if(spx<=size&&spy<=size)
		 		 b=false;
	 	  }while(b);
	 		return  new Position(spx, spy);
	 	 }
	  }
     catch (InputMismatchException e)
     {   System.out.print("坐标值应为整数，请重新输入：");
    	 in = new Scanner(System.in);
    	 spx = in.nextInt();
	 	 spy = in.nextInt();
	 	 if(spx<=size&&spy<=size)
		 	  return  new Position(spx, spy);
		 else
		 	 {  do
		 	   {
		 		 System.out.print("坐标值超出方格范围，请重输：");
		 		 in = new Scanner(System.in);
		 		 spx = in.nextInt();
			 	 spy = in.nextInt();
			 	 if(spx<=size&&spy<=size)
			 		 b=false;
		 	  }while(b);
		 		return  new Position(spx, spy);
           }
	 	
	}
}

//寻找布线路径 ,若找到start到finish的布线路径，返回true，否则返回false	
 static boolean findPath() {
	  if ((start.row == finish.row) && (start.col == finish.col)) {
			pathLen = 0;
			return true;
		}

		// 初始相对位移
		Position[] offset = new Position[4];
		offset[0] = new Position(-1, 0); // up
		offset[1] = new Position(1, 0); // down
		offset[2] = new Position(0, -1); // left
		offset[3] = new Position(0, 1); // right

		Position here = new Position(start.row, start.col);
		int numOfNbrs = 4; // 相邻方格数
		
		// 标记可达方格位置
		WireRouter.q = new LinkedList<Position>();
		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; //完成布线,跳出for循环
						
					q.add(new Position(nbr.row, nbr.col));
				}
			}

		 if ((nbr.row == finish.row) && (nbr.col == finish.col))
				break; // 完成布线选择，跳出do循环
							
			// 或节点队列是否为空
		if (q.isEmpty())
		   return false; // 没有结果
		
		here = (Position) q.remove(); // 获取下个可扩展结点
		 	
		} 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;
			for (int k = 0; k < numOfNbrs; k++) {
					nbr.row = here.row + offset[k].row;
					nbr.col = here.col + offset[k].col;
					if (grid[nbr.row][nbr.col] == j + 2)
						break;
				}
			 here = new Position(nbr.row, nbr.col); // 向前回溯！
			}	
		return true;
 }
 
static void print() {
	 System.out.println("▲表示起点,◎表示终点,●表示阻碍,□表示可用方格,★表示布线标记!");
	 for(int i=1;i<=size;i++)
	 { for(int j=1;j<=size;j++)
	    {    if(j==start.col&&i==start.row)
		    System.out.print("▲");
	    else if(j==finish.col&&i==finish.row)
	    		System.out.print("◎");
	    else if(grid[i][j]==1) 
		  System.out.print("●")	; 
		else if(grid[i][j]==-1)
			 System.out.print("★");
		else
			System.out.print("□");
	     }
	    System.out.println(); 
	    
	  }	 
	
}
//处理布线路径信息！
public void chuli(){
	   if (findPath()) {
		if(pathLen!=0){
		  System.out.println("布线路径长度为:" + pathLen);
		  System.out.print("start");
		  start.display();
		  System.out.print("-->");
		  for (int i = 0; i < path.length-1; i++) 
		  {
			path[i].display();
			System.out.print("-->");
			
			 grid[path[i].row][path[i].col]=-1;
		    	 
		  }
		  finish.display();
		  System.out.println();
		  print();
		  System.out.print("布线路径已标出，请查看！");
		}
		else
		  System.out.print("起点和原点相同，不用布线!");
		
	  } 
	 else
	 {      print();
		System.out.print("找不到布线路径!");
	  
	 }
 }

public static void main(String[] args)throws InputMismatchException {
	 int size;
	 Scanner sc;
	 Position st,fi;
     System.out.print("请输入方格大小: ");
	    sc=new Scanner(System.in);
	   try{
		   size=sc.nextInt();
	     }
	   catch(InputMismatchException e)
	   {  System.out.print("方格大小应为整数，请重新输入: ");
	      sc=new Scanner(System.in);
		  size=sc.nextInt();
	   }
    System.out.print("请输起点坐标：");
		st=WireRouter.input(size);
	System.out.print("请输终点坐标：");
		fi=WireRouter.input(size);
	
	 WireRouter wr=new WireRouter(size,st,fi);
	 wr.chuli();
	
}

}