bfs模板

import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	//设置从哪一个方向走过来的
  public static char[][]  source=new char[30][50];
  //设置行走方向 上下左右  
  /**
   * 最后的路径要是:在步数最少的前提下，请找出字典序最小的一个作为答案。
	 请注意在字典序中D<L<R<U。,所以我们也得按照这个顺序进行
	 将路径加入到队列中,这样才保证D要比L优先,L比R优先,R比U优先
   */
  static int[][] direct= {{1,0},{0,-1},{0,1},{-1,0}};
	public static void main(String[] args) throws FileNotFoundException {
		
		
		 
		//获取输入的数据
		
			Scanner str=new Scanner(new File("/Users/zhangxu/Desktop/a.txt"));
	
		
		int [][] numbers=new int[30][50];
		for(int i=0;i<source.length;i++) {
			String temString=str.nextLine();
			for(int j=0;j<source[i].length;j++) {
				numbers[i][j]=Integer.valueOf(temString.charAt(j)-48);
				
			}
		}
		//  初始化对象
		Location location=new Location(0, 0);
		//获取一个队列
		Queue<Location> queue=new LinkedList<Location>();
		queue.add(location);
		
		//记录是否走
		 int visited[][]=new int[30][50];
		 
		 //开始BFS
		 while(queue.size()>0) {
			//移除queue中的第一元素
			 Location curLocation=queue.poll();
				visited[curLocation.x][curLocation.y]=1;

			//然后遍历这个位置的四周可以走通的位置,
			 for(int i=0;i<direct.length;i++) {
					//如果这个位置的四个周围的节点是可以访问,那么假如队列里面
				 int x=curLocation.x+direct[i][0];
				 int y=curLocation.y+direct[i][1];
				 if(x>=numbers.length||x<0||y>=numbers[0].length||y<0||visited[x][y]!=0||numbers[x][y]==1) {
					 continue;
				 }
				 
				 //满足条件 添加到队列里面
				 //标记当前元素走过
				 visited[x][y]=1;
				 queue.add(new Location(x, y));
				 //添加到结果里面
				 source[x][y]=Source(i);

			 }
		 }
		 /**
		  * 如果是从结尾向着开始方向找,那么就只有一条路是通向开始的
		 * 所以我们从结尾开始找,那么最后还要将得到的字符串逆序
		  */
			StringBuffer path=new StringBuffer();
			int x=29,y=49;
			while(!(x==0 && y==0))
			{
				System.out.println(x+" "+y);
				char temp=source[x][y];
				path.append(temp);
				if(temp=='D')
					x --;
				if(temp=='L')
					y++;
				if(temp=='R')
					y--;
				if(temp=='U')
					x++;
			}
			System.out.println(path.reverse());
		 
		 
		 
		
	}
	private static char Source(int i) {
		if(i==0) {
			return 'D';
		}else if(i==1) {
			return 'L';
		}else if(i==2) {
			return 'R';
		}else {
			return 'U';
		}
		
	}
}  

class Location{
	int x;
	int y;
	public Location(int x,int y) {
		this.x=x;
		this.y=y;
	}
}