wirerouter.java

JAVA编程很好的实例啊

import java.util.*;

public class WireRouter 
{
	static class Position
	{
		public  int row;               //方格所在的行数
		public int col;               //方格所的列数
	
		Position(int rr,int cc)
		{
			row = rr;
			col = cc;
		}
		public void display()
		{
			System.out.print("(" + row + "," + col + ")" );
		}

	}

	private static int[][] grid ;        //方格阵列
	private static int size ;            //方格阵列的大小
	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;

	
	//队列的出队和入队
	static class  ArrayQueue 
   	{ 
   		private static final int defultSize=20;
     	private int size;                     
     	private int front;
     	private int rear;
     	private Position[] listArray;
     
     	ArrayQueue()
     	{
     		setup(defultSize);
     	}
     	ArrayQueue(int sz)
     	{
     		setup(sz);
     	}

     	void setup(int sz)
        {
      		size=sz+1;front=rear=0;listArray=new Position[sz+1];
        }
     	public void clear()
      	{
      		front=rear=0;
      	}
     	public  void Assert_notFalse(boolean p,String q)
     	{
     		if(!p)System.out.println((String)q);
     	}

     	public void put(Position it)
       	{
        	Assert_notFalse(((rear+1)% size)!=front,"Queue is full");
        	rear=(rear+1)%size;
        	listArray[rear]=it;
       	}
    	public Position remove()
       	{
        	Assert_notFalse(! isEmpty(),"Queue is empty ");
        	front=(front+1)%size;
        	return listArray[front];
       	}
    	public Position firstValue()
       	{
        	Assert_notFalse(! isEmpty(),"Queue is empty "); 
        	return listArray[(front+1)%size];
       	}
    	public boolean isEmpty()
       	{ 
       		return front==rear;
       	}
    	public void put(int k,int g)
       	{
       		Position itg=new Position(k,g);
       		put(itg);
       	}           
 
   }
   
   	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 the 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();
				}
   
	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;  //无解
			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 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 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.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)");*/

		WireRouter abc=new WireRouter();
		abc.inputDate();
		abc.findPath();
		System.out.print("布线的最短路径是：");
		System.out.println(pathLen);
		for(int i = 0;i < path.length;i++){
			path[i].display();
			System.out.print("--");
			}
	
	}
	

}