算法提高 哈哈哈 java 题解 978 bfs

算法提高 哈哈哈 java 题解 978 bfs

题目：
　　武侠学社里流行着一个冷笑话，爷爷对孙子说：“你知道金庸写的十四本书可以连成一副对联吗？飞雪连天射白鹿，笑书神侠倚碧鸳！”孙子不屑地说：“你知道JK罗琳写的七本书可以连成一句话吗？哈哈哈哈哈哈哈…”。这七个“哈”，代表着罗琳的哈利波特系列，书中的传奇魔法师哈利波特和队友一起，历经重重艰险，通过他们的智慧和宝物一次又一次的闯过难关。
　　时光如梭，哈利伙伴们也都长大了，他们四处游历，探寻各种迷宫。这日，他们来到一个迷宫，放眼望去，满地都是珍贵的宝物。这么多的宝物却无人拾取太不寻常了。有着丰富探险经验的他们强忍住拾取宝物的冲动，仔细观察，终于发现，迷宫里的宝物拾取必须按照一定的顺序。如，必须在拾取隐身衣后才能拾取飞天扫帚；只有在拥有飞天扫帚和变身水后，才能抓到吼叫信。幸运的是，赫敏认识所有的宝物，知道每一件宝物拾取的前提条件。
　　那么，哈利小队给出迷宫的地图以及迷宫中所有宝物的位置，同时赫敏列出所有宝物拾取的前提条件，请你帮助他们计算出他们拿完所有宝物，走出迷宫的最少步数。

输入格式

　　第一行为两个整数X和Y(3<=X,Y<=10)，表示迷宫的长和宽。
　　接下来X行，每一行为一个长度为Y的字符串，描述迷宫的状态。迷宫中，'#'表示墙，'.'表示通道, 'S'表示起点，'E'表示终点，'0'~'9'表示编号为0~9的宝物所在位置(同时也是通道)。在该迷宫的描述中，最外一周都为'#'，有且仅有唯一的'S'和'E'，'0'~'9'最多出现1次，并且数字p在迷宫中出现的前提是p为0或p-1在迷宫中出现。
　　接下来为N(0<=N<=10)行，用于描述图中出现的N个宝物拾取的前提条件。第i行描述编号i- 1的宝物的前提条件，首先为一个整数k，后面跟上k个整数a1, a2, ..., ak。其中0<=aj 输出格式

　　输入只有一行，如果哈利小队能成功拾取所有宝物并走出迷宫，则输出最少的步数。否则，输出"Impossible"。
Sample Input

4 5
#####
#SE2#
#031#
#####
2 1 3
0
1 0
1 1

Sample Output

9

---

解题思路：

要想按一定的顺序找出最少的步数，可以将每次找到一个宝物的最少步数累加起来，最终便能得到答案。

细节处理：

① 在输入时，对宝物信息的处理为了得到准确输入的行数，可以先在地图中找出宝物的数量。

② 因为需要多次用到两点之间的最少步数，可以单独写成一个方法。

③ 开始时第一个要找的宝物一定是不需要“先序”条件的，可以直接遍历所给的宝物信息，找为0的信息。

④ 开始点和结束点也可以作为“通路”走。

⑤ 不仅要找出下一步搜索的宝物，还需要通过遍历地图找到宝物所在的坐标。

⑥ 要判断bfs遍历完时是否已经到达终点，没到达说明没有通路，需要输出“Impossible”。

java代码：

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int m = Integer.parseInt(split[1]);
		char [][]arr = new char[n][m];
		int count = 0;
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			for(int j = 0; j < m; j++) {
				char ch = str.charAt(j);
				if(ch - '0' >= 0 && ch - '0' <= 9) {//读取宝物数量
					count++;
				}
				arr[i][j] = str.charAt(j);
			}
		}
		int [][]tag = new int[count][];//创建二维数组（不确定列数）
		for(int i = 0; i < count; i++) {
			split = br.readLine().split(" ");
			int num = Integer.parseInt(split[0]);
			tag[i] = new int[num];//创建列数
			for(int j = 1; j < split.length; j++) {
				tag[i][j - 1] = Integer.parseInt(split[j]);
			}
		}
		Temp978 obj = new Temp978(arr, tag);
		int ans = obj.bfs();
		if(ans != 0) {//不等于0表示有路径
			System.out.println(ans);
		}else {//表示无法到达
			System.out.println("Impossible");
		}
	}
}
class Temp978{
	char [][]arr;//地图
	int [][]tag;//寻找宝物时的先后顺序信息
	int num;//宝物数量
	int n;//地图行数
	int m;//列数
	boolean []vis;//标志宝物是否已被访问
	boolean [][]look;//标志地图的某一点是否已经被访问
	int []dx = new int[]{-1, 1, 0, 0};//上下左右四个方向
	int []dy = new int[]{0, 0, -1, 1};
	int ans = 0;//最终答案数
	
	public Temp978(char[][] arr, int[][] tag) {
		this.arr = arr;
		this.tag = tag;
		n = arr.length;
		m = arr[0].length;
		num = tag.length;
		vis = new boolean [num];
	}
	
	public int bfs() {//重载bfs，返回最终答案
		int count = 0;//已找到的宝物数量
		char first = ' ';//无先序条件的宝物，即可以直接找该宝物
		for(int i = 0; i < num; i++) {
			if(tag[i].length == 0) {
				first = (i + "").charAt(0);//找到后退出
				break;
			}
		}
		Point978 start = null;//广搜开始点
		Point978 end = null;//广搜结束点
		Point978 ended = null;//地图的出口
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(arr[i][j] == 'S') {
					start = new Point978(i, j, 0);//地图的起点
				}
				if(arr[i][j] == 'E') {//地图的终点
					ended = new Point978(i, j, 0);
				}
				if(arr[i][j] == first) {//地图上第一个找宝物的点
					end = new Point978(i, j, 0);
				}
			}
		}
		bfs(start, end);//从起点S到第一个宝物点的搜索
		vis[first - '0'] = true;//将该宝物点置为已访问，便于找到后继可以到达的宝物点
		char next = 'E';
		start = end;//前一个的结束点位下一轮的起点
		while(true) {
			if(count == num)break;//当宝物都找到时退出
			for(int i = 0; i < num; i++) {//找下一个已经满足条件的宝物点名称，例如1，或2……
				if(tag[i].length != 0) {
					int j = 1;
					for(j = 0; j < tag[i].length; j++) {
						if(!vis[tag[i][j]]) {
							break;
						}
					}
					if(j == tag[i].length && !vis[i]) {
						next = (i + "").charAt(0);
					}
				}
			}
			for(int i = 0; i < n; i++) {//找宝物点名称的坐标
				for(int j = 0; j < m; j++) {
					if(arr[i][j] == next) {
						end = new Point978(i, j, 0);
					}
				}
			}
			if(count > 0)vis[next - '0'] = true;//如果只有一个宝物，next将等于'E'，不处理会越界
			bfs(start, end);
			count++;
			start = end;
		}
		bfs(start, ended);//最后一个宝物点到终点的搜索
		return ans;
	}
	
	public void bfs(Point978 start, Point978 end) {//参数为起始点和终止点
		look = new boolean[n][m];//标志地图上的点是否已访问
		int endx = end.x, endy = end.y;
		Queue qu = new linkedList<>();
		qu.add(start);
		Point978 point = null;
		boolean flag = false;//用于标志最终是否到达了终点
		while(!qu.isEmpty()) {
			point = qu.poll();
			if(point.x == endx && point.y == endy) {
				flag = true;//标志为已到达
				break;
			}
			for(int i = 0; i < 4; i++) {//向该点的四个方向探测
				int x = point.x + dx[i];
				int y = point.y + dy[i];
				if(arr[x][y] != '#' && look[x][y] == false) {//不是#,并且未被访问过，则入队
					qu.add(new Point978(x, y, point.step + 1));//步数为上一步的step加一
					look[x][y] = true;//标志为已访问
				}
			}
		}
		if(flag) {//到达了终点，则将到达到终点的步数做累加
			ans += point.step;
		}else {//否则将结果重置
			ans = 0;
		}
	}
	
}
class Point978{//坐标类
	int x;
	int y;
	int step = 0;//保存当前坐标点到基数点的步数
	
	public Point978(int x, int y, int step) {
		this.x = x;
		this.y = y;
		this.step = step;
	}
}

提交截图：