华为机考第三题--迷宫路径(BFS)

前言

昨天做了华为的机考，前两题挺简单的，不像是考察算法，这个机考600分，100分及格，感觉像是送分题，这里不做详述，第三题就是迷宫两点间的最短路径，刚开始刷题，没见过，想着用递归，拿着他的测试样本怼递归，只通过了20%，参考了网上的[迷宫路径]，学习了一下并做个记录。

Input：
2,2 0,0 2,2 3 0,1 2,0 2,1
输入详解：
(2,2) 表示迷宫的长宽， (0,0)表示起点A，(2,2)表示终点B, 3 表示障碍的个数，后面的(1,2) (2,0) (2,1)表示障碍坐标，A可以上下左右移动，不能通过有障碍的坐标，找到达到B点的路径并打印
Output:
[0,0][1,0][1,1][1,2][2,2]

思路

用广度优先遍历(借助队列)实现，需要一个数据结构保存当前位置的坐标信息(x,y)，前一位置的信息pre。就是最短的感觉这个解法只是找到了第一次到达终点的路径，怎么保证他就是最短路径还有待学习，此处存疑 ，所以整个过程就先看代码理解一下吧。补充：依据BFS特性，第一次到达终点时的路径就是最短路径。前两天还不会的东西，去面试路上听大佬们讲讲，现在就有点理解了，多多笔试面试吧，越菜越要去，迎头赶上吧！

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

/** * @author jinhuajian * @data 2019年1月7日---下午7:44:03 * @blog https://me.csdn.net/qq_37119939 */
class Node {
	int x, y, dis;
	Node pre;

	public Node(int x, int y, int dis, Node pre) {
		this.x = x;
		this.y = y;
		this.dis = dis;
		this.pre = pre;
	}
}

public class main3_1 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
		String[] arr = s.split(" ");
		// System.out.println(arr[1]);
		int row = process(arr[0])[0] + 1;
		int col = process(arr[0])[1] + 1;
		int sr = process(arr[1])[0];
		int sc = process(arr[1])[1];
		int er = process(arr[2])[0];
		int ec = process(arr[2])[1];
		if (arr.length < 4)
			return;
		int[][] matrix = new int[row][col];
		for (int i = 4; i != arr.length; i++) {
			int[] tmp = process(arr[i]);
			matrix[tmp[0]][tmp[1]] = 1;// 障碍
		}
		bfs(matrix, sr, sc, er, ec);
	}
	// 3,3 0,0 3,3 4 0,3 1,0 1,2 2,2

	private static void bfs(int[][] matrix, int sr, int sc, int er, int ec) {
		int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 上下左右
		LinkedList<Node> queue = new LinkedList<Node>();
		Node start = new Node(sr, sc, 0, null);
		matrix[sr][sc] = 1;// 标记走过
		queue.offer(start);// 加入队列
		ok: while (!queue.isEmpty()) {
			Node tmp = queue.poll();
			for (int i = 0; i != move.length; i++) {// (1,2) 往上 (0,2)
				int x = tmp.x + move[i][0];
				int y = tmp.y + move[i][1];
				// 判断这一步是否合法
				if (x < 0 || x >= matrix[0].length || y < 0 || y >= matrix.length)
					continue;
				if (matrix[x][y] == 1)
					continue;
				Node next = new Node(x, y, tmp.dis + 1, tmp);
				if (x == er && y == ec) {
					queue.clear();// 清空用来存路径
					queue.offerFirst(next);// 尾从头插入
					Node preNode = next.pre;
					while (preNode != null) {
						queue.offerFirst(preNode);
						preNode = preNode.pre;
					}
					int res = queue.size() - 1;
					System.out.println("最短路径：" + queue.getLast().dis);
					for (Node n : queue) {
						System.out.print("[" + n.x + "," + n.y + "]");
					}
					break ok;// 跳出最外层的while循环，学到一招
				}
				matrix[x][y] = 1;// 标记走过
				queue.offer(next);// 加入队列

			}
		}

	}

	public static int[] process(String s) {
		int a = Integer.valueOf(s.charAt(0)) - 48;
		int b = Integer.valueOf(s.charAt(2)) - 48;
		return new int[] { a, b };
	}
}