random interviews: shortest path in a matrix

发表于 | 分类于

The task was to find the shortest path between x1,y1 and x2,y2 in a maze. You can move horizontally and vertically, where 1 is a wall and 0 is free space. output is k shortest steps to move from the start point to end point.

解法1：BFS

典型的BFS题目，用一个queue来解决。同时标记每一个已经visit过的元素的parent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
Java
{% codeblock lang:java %}
public List<List<Integer>> shortestPath(int[][] maze, int[] start, int[] end) {
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	if (maze == null || maze.length == 0 || maze[0].length == 0) {
		return res;
	}
	if (start[0] == end[0] && start[1] == end[1]) {
		List<Integer> temp = new ArrayList<Integer>(Arrays.asList(start));
		res.add(temp);
		return res;
	}
	int row = maze.length;
	int col = maze[0].length;
	// Use a map to store each point's shortest parent from the start point
	Map<List<Integer>, List<Integer>> map = new HashMap<List<Integer>, List<Integer>>();
	int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
	List<Integer> temp = new ArrayList<Integer>(Arrays.asList(start));
	map.put(temp, null);
	Queue<List<Integer>> queue = new LinkedList<List<Integer>>();
	queue.offer(temp);
	maze[start[0]][start[1]] = -1;
	while(!queue.isEmpty()) {
		int size = queue.size();
		for (int i = 0; i < size; ++i) {
			List<Integer> cur = queue.poll();
			for (int j = 0; j < directions.length; ++j) {
				int x = cur.get(0) + directions[j][0];
				int y = cur.get(1) + directions[j][1];
				if (x >= 0 && x < row && y >= 0 && y < col && maze[x][j] != -1) {
					ArrayList<Integer> temp = new ArrayList<Integer>(Arrays.asList(x,y));
					if (x == end[0] && y == end[1]) {
						// find the destination
						res = getPath(map, temp);
						return res;
					}
					queue.offer(temp);
					map.put(temp, cur);
					maze[x][y] = -1; // mark as visited
				}
			}
		}
	}
	return res;
}
private List<List<Integer>> getPath(HashMap<List<Integer>, List<Integer>> map, List<Integer> end) {
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	List<Integer> cur = end;
	while(map.get(cur) != null) {
		res.add(cur);
		cur = map.get(cur);
	}
	return res;
}
{% endcodeblock %}