490. The Maze

Question

Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)

Output: true

Thinking:

• Method: DFS

public class TheMaze {
	public static boolean hasPath(int[][] maze, int[] start, int[] destination){
		if(maze == null || maze.length == 0) return false;
		int height = maze.length;
		int width = maze[0].length;
		return searchDFS(maze, start, destination, new boolean[height][width]);
	}
	private static boolean searchDFS(int[][] maze, int[] start, int[] des, boolean[][] used){
		if(start[0] == des[0] && start[1] == des[1]) return true;
		used[start[0]][start[1]] = true;
		List<Integer> around = findPath(maze, start, used);
		boolean result = false;
		for(Integer index : around){
			int row = index / maze[0].length;
			int col = index % maze[0].length;
			result |= searchDFS(maze, new int[]{row, col},  des, used);
			if(result) return true;
		}
		return false;
	}
	private static List<Integer> findPath(int[][] maze, int[] pos, boolean[][] used){
		int height = maze.length;
		int width = maze[0].length;
		List<Integer> result = new ArrayList<>();
		if(pos[0] > 0)
			if(!used[pos[0] - 1][pos[1]] && maze[pos[0] - 1][pos[1]] == 0)
				result.add((pos[0] - 1) * width + pos[1]);
		if(pos[0] + 1 < height)
			if(!used[pos[0] + 1][pos[1]] && maze[pos[0] + 1][pos[1]] == 0)
				result.add((pos[0] + 1) * width + pos[1]);
		if(pos[1] > 0)
			if(!used[pos[0]][pos[1] - 1] && maze[pos[0]][pos[1] - 1] == 0)
				result.add(pos[0] * width + pos[1] - 1);
		if(pos[1] + 1 < width)
			if(!used[pos[0]][pos[1] + 1] && maze[pos[0]][pos[1] + 1] == 0)
				result.add(pos[0] * width + pos[1] + 1);
		return result;
	}
}

• Method2 ： BFS

private static boolean searchBFS(int[][] maze, int[] start, int[] des, boolean[][] used){
		LinkedList<Integer> q = new LinkedList<>();
		int height = maze.length;
		int width = maze[0].length;
		q.add(start[0] * width + start[1]);
		while(!q.isEmpty()){
			Integer cur = q.poll();
			int row = cur / width, col = cur % width;
			used[row][col] = true;
			if(row == des[0] && col == des[1]) return true;
			q.addAll(findPath(maze, new int[]{row, col}, used));
		}
		return false;
	}