Snap 面经题目:maze

0002505492

题目:
问题一个走迷宫问题。给了一个矩阵,”1″代表起点,位于左上角;”9″代表重点,位于右下角;”0″代表通路,”5″代表墙。. 鍥磋鎴戜滑@1point 3 acres
矩阵长得是这样
[
[1, 5, 5, 5, 5, 0],
[0, 5, 0, 5, 5, 0],
[0, 5, 0, 0, 0, 0],
[0, 5, 0, 0, 5, 0],
[0, 0, 0, 5, 0, 9]
]
设计一个算法,看看这个迷宫能不能从起点走到重点。要求输出路径。

思路:
使用backtrace 和 DFS。

代码:

import java.util.*;
public class Solution {
	static int m, n;
	static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1},{0, -1}};
	public static List> canReach(int[][] maze)
	{
		if(maze == null || maze.length == 0) return null;
		m = maze.length;
		n = maze[0].length;
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(maze[i][j] == 1)
				{
					List> res = new ArrayList<>();
					if(DFS(i, j, maze, res))
					{
						maze[i][j] = 1;
						return res;
					}
					maze[i][j] = 1;
				}
			}
		}
		return null;
	}
	
	private static boolean DFS(int i, int j, int[][] maze, List> res)
	{
		List list = new ArrayList<>();
		list.add(i);
		list.add(j);
		res.add(list);
		if(maze[i][j] == 9) return true;
		maze[i][j] = 5;
		for(int k = 0; k < 4; k++)
		{
			int x = i + dir[k][0];
			int y = j + dir[k][1];
			if(x >= 0 && x < m && y >=0 && y < n && maze[x][y] != 5)
			{
				if(DFS(x, y ,maze, res))
				{
					maze[i][j] = 0;
					return true;
				}
			}
		}
		maze[i][j] = 0;
		res.remove(res.size() - 1);
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] input = {{1, 5, 5, 5, 5, 0},{0, 5, 0, 5, 5, 0},{0, 5, 0, 0, 0, 0},{0, 5, 0, 0, 5, 0},{0, 0, 0, 5, 0, 9}};
//		System.out.println(canReach(input));
		List> output = canReach(input);
		for(List list : output)
		{
			for(int i : list) System.out.print(i);
			System.out.println("");
		}
	}

}

Output:

00
10
20
30
40
41
42
32
22
23
24
25
35
45

468total visits,1visits today