LintCode 1479 · Can Reach The Endpoint.java

	public class Solution {
	/**
	* @param map: the map
	* @return: can you reach the endpoint
	*/
	public boolean reachEndpoint(int[][] map) {
	// Write your code here
	if (map == null || map.length == 0 || map[0] == null || map[0].length == 0 ) {
	return true;
	}
	if (map[0][0] == 0) {
	return false;
	}
	return bfs(map);
	}
	int[] dx = new int[]{1, -1, 0, 0};
	int[] dy = new int[]{0, 0, 1, -1};
	private boolean bfs(int[][] map) {
	int n = map.length;
	int m = map[0].length;
	Queue<Integer> queue = new ArrayDeque<>();
	Set<Integer> visited = new HashSet<>();
	queue.add(0);
	visited.add(0);
	while (!queue.isEmpty()) {
	int codedIndex = queue.poll();
	int i = codedIndex / m;
	int j = codedIndex % m;
	for (int k = 0; k < 4; k++) {
	int x = i + dx[k];
	int y = j + dy[k];
	if (!isValid(x, y, n, m) || map[x][y] == 0 || visited.contains(x * m + y)) {
	continue;
	}
	if (map[x][y] == 9) {
	return true;
	}
	queue.add(x * m + y);
	visited.add(x * m + y);
	}
	}
	return true;
	}
	private boolean isValid(int i,int j,int n,int m) {
	return i >= 0 && i < n && j >= 0 && j < m;
	}
	}

view raw LintCode 1479 · Can Reach The Endpoint.java hosted with ❤ by GitHub