首页 > 代码库 > bfs

bfs

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;/** *  * @author ramanu_jan * *//** * 四维点 */class Point{	int x, y, z, w;		public Point(int x, int y, int z, int w){		this.x=x;	this.y=y;	this.z=w;	this.w=w;	}		public Point(Point p){ assign(p); }		public void assign(Point p){		x=p.x;	y=p.y;	z=p.z;	w=p.w;	}	@Override	public boolean equals(Object obj) {		if(null == obj) return false;		if(obj instanceof Point){			Point p = (Point)obj;			return p.x==x && p.y==y && p.z==z && p.w==w;		}		return false;	}}public class Main {	private int n, m;				//	private Point[][][][] pre;		//前向索引,访问与否标记	private Point s;				//开始位置	private String[] g;				//图	private static int[] dx = {1, 0, 0, -1},						 dy = {0, -1, 1, 0};	//位移方向	private static String opt = "DLRU";			//操作序列		private boolean cango(int x, int y){		return x>-1 && x<n && y>-1 && y<m && g[x].charAt(y)!=‘#‘;	}		private Point bfs(){		pre = new Point[n+1][m+1][n+1][m+1];		s = new Point(-1, -1, -1, -1);		/**		 * -1标记未访问		 */		for(int x = 0; x < n; x++) for(int y = 0; y < m; y++) for(int z = 0; z < n; z++)			for(int w = 0; w < m; w++) pre[x][y][z][w] = new Point(s); 		Queue<Point> q = new LinkedList<Point>();		/**		 * 找到两个点位置		 */		outer:	for(int i = 0, cnt = 0; i < n; i++)					for(int j = 0; j < m; j++) if(g[i].charAt(j) == ‘*‘){						if(cnt++ == 0){							s.x = i;	s.y = j;						}else{							s.z = i;	s.w = j;							pre[s.x][s.y][s.z][s.w].assign(s);							q.add(new Point(s));	break outer;						}					}		/**		 * 暴力最短路		 */		while(!q.isEmpty()){			Point p = q.remove();			if(p.x == p.z && p.y == p.w) return p;			for(int i = 0; i < 4; i++){				Point np = new Point(p);				if(cango(np.x+dx[i], np.y+dy[i])){					np.x+=dx[i];	np.y+=dy[i];				}				if(cango(np.z+dx[i], np.w+dy[i])){					np.z+=dx[i];	np.w+=dy[i];				}				if(!np.equals(p) && pre[np.x][np.y][np.z][np.w].x<0){					q.add(np); 	pre[np.x][np.y][np.z][np.w].assign(p);				}			}		}		return new Point(-1, -1, -1, -1);	}		/**	 * 输出答案	 */	private void solve(){		Point p = bfs();		if(p.x < 0){			System.out.println("Sorry");		}else{			String ans = "", res="";			while(!p.equals(s)){				Point b = new Point(pre[p.x][p.y][p.z][p.w]);				for(int i = 0; i < 4; i++){					Point np = new Point(b);					if(np.x!=p.x || np.y!=p.y){						np.x+=dx[i];	np.y+=dy[i];					}					if(np.z!=p.z || np.w!=p.w){						np.z+=dx[i];	np.w+=dy[i];					}					if(np.equals(p)){						ans += opt.charAt(i);							p = b;		break;					}				}			}			for(int i = ans.length() - 1; i > -1; i--){				res += ans.charAt(i);			}			System.out.println(res);		}	}		private void xtu1187(){		Scanner sc = new Scanner(System.in);		while(sc.hasNext()){			n = sc.nextInt();  m = sc.nextInt();			g = new String[12];			for(int i = 0; i < n; i++) g[i] = sc.next();			solve();		}	}		public static void main(String[] args) {		new Main().xtu1187();	}}

 

 

题目描述

一个迷宫里,有两个点,你的任务是给出尽可能短的一系列的命令,让这两个点一起执行这些命令能走到一起。如果某个点按某个命令走会走出迷宫或走到障碍上,则忽略这条命令。

输入

输入不超过1000个样例,每个样例第一行有两个整数n,m(2≤n,m≤11),之后n行每行m个字符,‘.‘表示能走的地方,‘#‘表示障碍,‘*‘表示其中一个点。每个样例之间有一个空行。

输出

每个样例输出一行,包含‘U‘,‘D‘,‘L‘,‘R‘。‘U‘表示向上走的命令,‘D‘表示向下,‘L‘表示向左,‘R‘表示向右。要是有多个答案,输出字典序最小的序列。如果无法达到目标,输出“Sorry”(引号不要输出)。

样例输入

4 11*.##..#..#*...#..#.#...##.#.#.##.##..###....4 4.*...###...*....10 10*.........#########............#########..........#########............#########.........*##########

样例输出

SorryLLLUULLLLLLLLLUURRRRRRRRRUULLLLLLLLLUURRRRRRRRRDD

bfs