BFS
Last updated
Was this helpful?
Last updated
Was this helpful?
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
if (rooms == null || rooms.size() == 0) {
return true;
}
Set<Integer> visited = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
q.offer(0);
visited.add(0);
while (!q.isEmpty()) {
int curt = q.poll();
for (int next : rooms.get(curt)) {
if (!visited.contains(next)) {
q.offer(next);
visited.add(next);
}
}
}
return visited.size() == rooms.size();
} public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
if (grid.length == 1 && grid[0][0] == 0) return 1;
boolean[][] visited = new boolean[n][n];
visited[0][0] = true;
int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0},{1,1}, {-1,-1}, {1,-1}, {-1,1}};
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0});
int step = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curt = q.poll();
for (int[] d : dir) {
int nx = curt[0] + d[0];
int ny = curt[1] + d[1];
if (inbound(grid, nx, ny) && !visited[nx][ny] && grid[nx][ny] == 0) {
if (nx == n - 1 && ny == n - 1) return step + 1;
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
step++;
}
return -1;
}
private boolean inbound(int[][] m, int x, int y) {
return x >= 0 && y >= 0 && x < m.length && y < m[0].length;
}Count the number of oranges and rotten oranges. Starting with all rotten oranges in the queue, traverse in level order to fill all good oranges. Return the number of levels if the all oranges are rotten (check count).
int[][] dirs = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.offer(new int[]{i, j});
else if (grid[i][j] == 1) count++;
}
}
if (count == 0) return 0;
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curt = q.poll();
for (int[] d : dirs) {
int nx = curt[0] + d[0];
int ny = curt[1] + d[1];
if (nx >= 0
&& nx < m
&& ny >= 0
&& ny < n
&& grid[nx][ny] == 1) {
grid[nx][ny] = 2;
count--;
q.offer(new int[]{nx, ny});
}
}
}
step++;
}
return count == 0 ? step - 1 : -1;
} directions = [[0,1],[1,0],[-1,0], [0,-1]]
def orangesRotting(self, grid: List[List[int]]) -> int:
queue = []
orange = 0
for x in range(0, len(grid)):
for y in range(0, len(grid[0])):
if grid[x][y] == 2:
queue.append([x, y])
if grid[x][y] == 1:
orange += 1
if orange == 0:
return 0
level = 0
while queue:
size = len(queue)
for k in range(0, size):
curtx, curty = queue.pop(0)
if grid[curtx][curty] == 1:
grid[curtx][curty] = 2
orange -= 1
if orange == 0:
return level
for d in self.directions:
nx = curtx + d[0]
ny = curty + d[1]
if self.inbound(grid, nx, ny) and grid[nx][ny] == 1:
queue.append([nx, ny])
level += 1
if orange == 0:
return level
return -1
def inbound(self, grid, x, y) :
return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) Given a 2D boolean array where true represents water and false represents land, generate a grid with highest possible peak. Rules are:
the height of any water cell is 0.
the height of any land cell cannot differ for more than one from any of the neighboring (sharing one edge) cells.
Add all "T" nodes into a BFS queue and trigger a BFS from all those nodes. Also, maintain the distance used to reach each node alongside. Once the BFS visits all the nodes, return the distance to reach every node as the answer.
For the followup:- From all the nodes that have reached max peak height, trigger another BFS that goes from max peak height node to other nodes decrementing the distance. This would lead to more nodes having a height of 0
int[][] directions = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
public int maxDistance(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) return -1;
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
Queue<int[]> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
int count0 = 0, count1 = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
q.offer(new int[]{i, j});
visited.add(i * n + j);
count1++;
} else {
count0++;
}
}
}
int res = -1;
if (count0 == 0 || count1 == 0) return res;
int level = -1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curt = q.poll();
for (int[] d : directions) {
int nx = curt[0] + d[0];
int ny = curt[1] + d[1];
if (inbound(grid, nx, ny)
&& !visited.contains(nx * n + ny) && grid[nx][ny] == 0) {
q.offer(new int[]{nx, ny});
visited.add(nx * n + ny);
}
}
}
level++;
}
return level;
}
private boolean inbound(int[][] matrix, int x, int y) {
return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
} directions = [[0,1],[1,0],[-1,0], [0,-1]]
def wallsAndGates(self, rooms: List[List[int]]) -> None:
queue = []
for x in range(0, len(rooms)):
for y in range(0, len(rooms[0])):
if (rooms[x][y] == 0):
queue.append([x, y])
level = 0
while queue:
size = len(queue)
for k in range(0, size):
curtx, curty = queue.pop(0)
if rooms[curtx][curty] == 2147483647:
rooms[curtx][curty] = level
for d in self.directions:
nx = curtx + d[0]
ny = curty + d[1]
if self.inbound(rooms, nx, ny) and rooms[nx][ny] == 2147483647:
queue.append([nx, ny])
level += 1
return
def inbound(self, grid, x, y) :
return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) directions = [[0,1],[1,0],[-1,0], [0,-1]]
def solve(self, board: List[List[str]]) -> None:
if not board or len(board) == 0 or len(board[0]) == 0:
return
m = len(board)
n = len(board[0])
queue = []
for i in range(0, m):
if board[i][0] == "O":
queue.append([i, 0])
if board[i][n - 1] == "O":
queue.append([i, n - 1])
for j in range(0, n):
if board[0][j] == "O":
queue.append([0, j])
if board[m - 1][j] == "O":
queue.append([m - 1, j])
while queue:
x, y = queue.pop(0)
board[x][y] = "B"
for d in self.directions: ## x= 3,y=1
nx = x + d[0]
ny = y + d[1]
if self.inbound(board, nx, ny) and board[nx][ny] == "O":
queue.append([nx, ny])
for i in range(0, m):
for j in range(0, n):
if board[i][j] == "O":
board[i][j] = "X"
if board[i][j] == "B":
board[i][j] = "O"
def inbound(self, grid, x, y) :
return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
// Write your code here
Queue<UndirectedGraphNode> q = new LinkedList<>();
Set<UndirectedGraphNode> visited = new HashSet<>();
q.offer(A);
visited.add(A);
int level = 0;
while (!q.isEmpty()) {
level++;
int size = q.size();
for (int i = 0; i < size; i++) {
UndirectedGraphNode curt = q.poll();
for (UndirectedGraphNode next : curt.neighbors) {
if (next == B) {
return level;
}
if (visited.contains(next)) {
continue;
}
visited.add(next);
q.offer(next);
}
}
}
return -1;
} def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
visit = set()
queue = []
queue.append(startUrl)
visit.add(startUrl)
host = startUrl.split("/")[2]
res = []
while queue:
curt = queue.pop(0)
res.append(curt)
for next in htmlParser.getUrls(curt):
if next not in visit and host in next:
queue.append(next)
visit.add(next)
return res public List<String> crawl(String startUrl, HtmlParser htmlParser) {
Set<String> visited = new HashSet<>();
String hostname = startUrl.split("/")[2];
Queue<String> q = new LinkedList<>();
q.offer(startUrl);
while (!q.isEmpty()) {
String curt = q.poll();
visited.add(curt);
for (String next : htmlParser.getUrls(curt)) {
if (next.indexOf(hostname) != -1 && !visited.contains(next)) {
q.offer(next);
}
}
}
return new ArrayList<>(visited);
} int[][] directions = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
List<List<Integer>> result = new ArrayList<>();
Queue<int[]> q_P = new LinkedList<>();
Queue<int[]> q_A = new LinkedList<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (i == 0 || j == 0) {
q_P.offer(new int[]{i, j});
pacific[i][j] = true;
}
if (i == m - 1 || j == n - 1) {
q_A.offer(new int[]{i, j});
atlantic[i][j] = true;
}
}
}
BFS(matrix, q_P, pacific);
BFS(matrix, q_A, atlantic);
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(Arrays.asList(new Integer[]{i, j}));
}
}
}
return result;
}
private void BFS(int[][] matrix, Queue<int[]> q, boolean[][] visited) {
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curt = q.poll();
int x = curt[0], y = curt[1];
for (int[] d : directions) {
int nx = x + d[0];
int ny = y + d[1];
if (inbound(matrix, nx, ny)
&& matrix[nx][ny] >= matrix[x][y]
&& !visited[nx][ny]) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
}
private boolean inbound(int[][] matrix, int x, int y) {
return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
}Build graph by using stop to next available stops. Level order BFS to find the next stops, return step/level when reach stop T. (This answer will return TLE when there are too many stops)
public int numBusesToDestination(int[][] routes, int S, int T) {
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int[] route : routes) {
for (int i = 0; i < route.length; i++) {
for (int j = 0; j < route.length; j++) {
if (i == j) continue;
map.putIfAbsent(route[i], new HashSet<>());
map.putIfAbsent(route[j], new HashSet<>());
map.get(route[i]).add(route[j]);
map.get(route[j]).add(route[i]);
}
}
}
Queue<Integer> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
q.offer(S);
int level = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int curt = q.poll();
if (curt == T) return level;
if (map.get(curt) == null) continue;
for (int next : map.get(curt)) {
if (next == T) return level + 1;
if (visited.contains(next)) continue;
visited.add(next);
q.offer(next);
}
}
level++;
}
return -1;
}One modification is to check duplicate on bus route, instead of bus stops. That will eliminate lots of path since all stops on traveled path are redundant.
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T) return 0;
Map<Integer, Set<Integer>> map = new HashMap<>(); // stop : buses
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < routes.length; i++) {
for (int n : routes[i]) {
map.putIfAbsent(n, new HashSet<>());
map.get(n).add(i);
}
}
if (!map.containsKey(S)) return -1;
Set<Integer> visited = new HashSet<>();
int count = 0;
q.offer(S);
while (!q.isEmpty()) {
int size = q.size();
for (int k = 0; k < size; k++) {
int curt = q.poll();
if (curt == T) return count + 1;
for (int r : map.get(curt)) {
if (visited.contains(r)) continue;
visited.add(r);
for (int next : routes[r]) {
if (next == T) return count + 1;
q.offer(next);
}
}
}
count++;
}
return -1;
}N is number of stops, T is the stops * edges: T: O(n^2)
Find the next node by extending the directions, until reach boundary or wall. Use boolean[][] visited to record all visited nodes.
int[][] dirs = {{1,0} , {0,1}, {-1,0}, {0,-1}};
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean[][] visited = new boolean[maze.length][maze[0].length];
Queue<int[]> q = new LinkedList<>();
q.offer(start);
visited[start[0]][start[1]] = true;
while (!q.isEmpty()) {
int[] curt = q.poll();
if (curt[0] == destination[0] && curt[1] == destination[1]) {
return true;
}
for (int[] dir : dirs) {
int x = curt[0];
int y = curt[1];
while (inbound(maze, x + dir[0], y + dir[1])
&& maze[x + dir[0]][y + dir[1]] != 1) {
x += dir[0];
y += dir[1];
}
if (x == destination[0] && y == destination[1]) {
return true;
}
if (!visited[x][y]) {
visited[x][y] = true;
q.offer(new int[]{x, y});
}
}
}
return false;
}
private boolean inbound(int[][] maze, int x, int y) {
return x >= 0 && y >= 0 && x < maze.length && y < maze[0].length;
}The BFS solution requires to store all path to destination. Use a dist matrix to store the minimum distance between each grid and start point. Replace the distance when new calculated steps is less than the earlier calculations. Output result as all distances are calculated.
int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
if (start == null || destination == null || maze == null || maze.length == 0 || maze[0].length == 0) {
return -1;
}
int m = maze.length, n = maze[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
Queue<int[]> q = new LinkedList<>();
q.offer(start);
dist[start[0]][start[1]] = 0;
while (!q.isEmpty()) {
int[] curt = q.poll();
for (int[] d : direction) {
int nx = curt[0];
int ny = curt[1];
int step = 0;
while (inbound(maze, nx + d[0], ny + d[1]) && maze[nx + d[0]][ny + d[1]] == 0) {
nx += d[0];
ny += d[1];
step++;
}
if (dist[nx][ny] > dist[curt[0]][curt[1]] + step) {
dist[nx][ny] = dist[curt[0]][curt[1]] + step;
q.offer(new int[]{nx, ny});
}
}
}
return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1
: dist[destination[0]][destination[1]];
}
private boolean inbound(int[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}Given a knight in a chessboard (a binary matrix with 0as empty a 1as barrier) with a source position, find the shortest path to a destination position, return the length of the route.
Return -1 if knight can not reached.
Notice
Source and destination must be empty.
Knight can not enter the barrier.
int[][] directions = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1},
{1, -2}, {2, -1}, {-1, -2}, {-2, -1}};
public int knightshortestpath(int[][] grid, int[] start, int[] destination) {
if(grid == null || grid.length == 0 ||
grid[0].length == 0 || start == null || destination == null){
return -1;
}
if (start[0] == destination[0] && start[1] == destination[1]) {
return 0;
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
grid[start[0]][start[1]] = 2;
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curt = queue.poll();
for (int[] d : directions) {
int nx = curt[0] + d[0];
int ny = curt[1] + d[1];
if (nx == destination[0] && ny == destination[1]) {
return level + 1;
}
if (inbound(grid, nx, ny) && grid[nx][ny] == 0) {
grid[nx][ny] = 2;
queue.offer(new int[]{nx, ny});
}
}
}
level++;
}
return -1;
}
private boolean inbound(int[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}Fill the result matrix with Integer.MAX_VALUE to detect if the node has been visited. Starting from 0 grids, use BFS to detect if the next distance from 0 is larger than expected, if so, correct it to the right value. Offer that next node to the queue.
T: O(m * n) S: O(m * n)
int[][] dirs = {{1,0} , {0,1}, {-1,0}, {0,-1}};
public int[][] updateMatrix(int[][] matrix) {
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
q.offer(new int[]{i, j});
} else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
while (!q.isEmpty()) {
int[] curt = q.poll();
for (int[] d : dirs) {
int nx = curt[0] + d[0];
int ny = curt[1] + d[1];
if (inbound(matrix, nx, ny) && matrix[nx][ny] > matrix[curt[0]][curt[1]] + 1) {
matrix[nx][ny] = matrix[curt[0]][curt[1]] + 1;
q.offer(new int[]{nx, ny});
}
}
}
return matrix;
}
private boolean inbound(int[][] matrix, int x, int y) {
return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
}T: O(k^2 * N) N is number of words and k is the average length of words
public int ladderLength(String beginWord,
String endWord,
List<String> wordList) {
if (beginWord == null || endWord == null
|| beginWord.isEmpty() || endWord.isEmpty()) {
return 0;
}
if (beginWord.equals(endWord)) return 0;
Set<String> dict = new HashSet<>();
dict.addAll(wordList);
if (!dict.contains(endWord)) return 0;
Set<String> visited = new HashSet<>();
visited.add(beginWord);
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
int level = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String curt = q.poll();
for (String next : getNexts(curt, dict)) {
if (next.equals(endWord)) return level + 1;
if (visited.contains(next)) continue;
visited.add(next);
q.offer(next);
}
}
level++;
}
return 0;
}
private Set<String> getNexts(String s, Set<String> dict) {
Set<String> result = new HashSet<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
char old = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String next = String.valueOf(chars);
if (dict.contains(next)) result.add(next);
}
chars[i] = old;
}
return result;
} def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
dic = set(wordList)
if endWord not in dic:
return 0
queue = []
visit = set()
queue.append(beginWord)
visit.add(beginWord)
level = 1
while queue:
size = len(queue)
for i in range(size):
curt = queue.pop(0)
for next in self.getNext(curt, dic, visit):
if next == endWord:
return level + 1
if next in dic and next not in visit:
visit.add(next)
queue.append(next)
level += 1
return 0
def getNext(self, s, dic, visit):
res = []
for i in range(len(s)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new = s[:i] + c + s[i + 1:]
if new in dic and new not in visit:
res.append(new)
return resUse BFS level order traversal to build graph and record distance from start node. DFS to build path.
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Map<String, Integer> dist = new HashMap<>();
Map<String, Set<String>> graph = new HashMap<>();
Set<String> dict = new HashSet<>();
dict.addAll(wordList);
List<List<String>> res = new ArrayList<>();
if (!dict.contains(endWord) || beginWord.equals(endWord)) return res;
bfsBuildGraph(beginWord, endWord, dict, dist, graph);
List<String> list = new ArrayList<>();
list.add(beginWord);
dfs(beginWord, endWord, list, res, dist, graph);
return res;
}
private void dfs(String curt,
String target,
List<String> list,
List<List<String>> result,
Map<String, Integer> dist,
Map<String, Set<String>> graph) {
if (curt.equals(target)) {
result.add(new ArrayList<>(list));
return;
}
if (graph.get(curt) == null) return;
for (String next : graph.get(curt)) {
if (dist.get(next) == dist.get(curt) + 1) {
list.add(next);
dfs(next, target, list, result, dist, graph);
list.remove(list.size() - 1);
}
}
}
private void bfsBuildGraph(String beginWord,
String endWord,
Set<String> dict,
Map<String, Integer> dist,
Map<String, Set<String>> graph) {
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
dist.put(beginWord, 0);
boolean foundEnd = false;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String curt = q.poll();
int d = dist.get(curt);
graph.putIfAbsent(curt, new HashSet<>());
for (String next : getNexts(curt, dict)) {
graph.get(curt).add(next);
if (next.equals(endWord)) foundEnd = true;
if (dist.containsKey(next)) continue;
dist.put(next, d + 1);
q.offer(next);
}
}
if (foundEnd) break;
}
}
private Set<String> getNexts(String s, Set<String> dict) {
Set<String> result = new HashSet<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
char old = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String next = String.valueOf(chars);
if (dict.contains(next)) result.add(next);
}
chars[i] = old;
}
return result;
}Use a map to store the relationship key: current node value: corresponding new node. Traverse the graph with a curt node and add corresponding neighbors to the neighbors list.
T: O(n)
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
Queue<Node> q = new LinkedList<>();
map.put(node, new Node(node.val, new ArrayList<>()));
q.offer(node);
while (!q.isEmpty()) {
Node curt = q.poll();
for (Node next : curt.neighbors) {
if (!map.containsKey(next)) {
map.put(next, new Node(next.val, new ArrayList<>()));
q.offer(next);
}
map.get(curt).neighbors.add(map.get(next));
}
}
return map.get(node);
} def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None
dic = {}
visited = set()
queue = []
queue.append(node)
visited.add(node)
dic[node] = Node(node.val)
while queue:
curt = queue.pop(0)
for next in curt.neighbors:
if next not in visited:
dic[next] = Node(next.val)
queue.append(next)
visited.add(next)
dic[curt].neighbors.append(dic[next])
return dic[node] public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) {
return false;
}
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
map.putIfAbsent(u, new HashSet<>());
map.putIfAbsent(v, new HashSet<>());
map.get(u).add(v);
map.get(v).add(u);
}
Set<Integer> visited = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
q.offer(0);
visited.add(0);
while (!q.isEmpty()) {
int curt = q.poll();
if (map.get(curt) == null) continue;
for (int next : map.get(curt)) {
map.get(next).remove(curt);
if (visited.contains(next)) {
return false;
}
visited.add(next);
q.offer(next);
}
}
return visited.size() == n;
} def validTree(self, n: int, edges: List[List[int]]) -> bool:
if n != len(edges) + 1:
return False
graph = [[] for i in range(n)]
indegree = [0] * n
for v, u in edges:
graph[u].append(v)
graph[v].append(u)
queue = []
visited = set()
queue.append(0)
visited.add(0)
while queue:
curt = queue.pop(0)
for next in graph[curt]:
if next in visited:
return False
graph[next].remove(curt)
visited.add(next)
queue.append(next)
return len(visited) == nConvert index to board by using:
int row = n - (next - 1) / n - 1
int col = (n - row) % 2 != 0 ? (next - 1) % n : n - (next - 1) % n - 1
public int snakesAndLadders(int[][] board) {
if (board == null || board.length == 0) return 0;
int n = board.length;
Queue<Integer> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
q.offer(1);
visited.add(1);
int step = 0, min = Integer.MAX_VALUE;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int curt = q.poll();
if (curt == n * n) min = Math.min(min, step);
for (int k = 1; k <= 6; k++) {
int next = curt + k;
if (next > n * n) break;
if (visited.contains(next)) continue;
visited.add(next);
int row = n - (next - 1) / n - 1;
int col = (n - row) % 2 != 0 ? (next - 1) % n
: n - (next - 1) % n - 1;
if (board[row][col] == curt) continue;
if (board[row][col] == -1) {
q.offer(next);
} else {
q.offer(board[row][col]);
}
}
}
step++;
}
return min == Integer.MAX_VALUE ? -1 : min;
}Similar as 127. Word Ladder.
public int openLock(String[] deadends, String target) {
Set<String> deads = new HashSet<>();
for (String d : deadends) {
if (d.equals("0000")) {
return -1;
}
deads.add(d);
}
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer("0000");
visited.add("0000");
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curt = queue.poll();
if (curt.equals(target)) return level;
for (String next : getNexts(curt, deads, visited)) {
if (visited.contains(next)) {
continue;
}
visited.add(next);
queue.offer(next);
}
}
level++;
}
return -1;
}
private Set<String> getNexts(String curt, Set<String> deads, Set<String> visited) {
Set<String> nextCurs = new HashSet<>();
char[] chars = curt.toCharArray();
for (int i = 0; i < 4; i++) {
char origin = chars[i];
chars[i] = (char)((origin - '0' + 1) % 10 + '0');
String next = new String(chars);
if (!deads.contains(next) && !visited.contains(next)) {
nextCurs.add(next);
}
chars[i] = (char)((origin - '0' - 1 + 10) % 10 + '0');
next = new String(chars);
if (!deads.contains(next) && !visited.contains(next)) {
nextCurs.add(next);
}
chars[i] = origin;
}
return nextCurs;
} def openLock(self, deadends: List[str], target: str) -> int:
start = "0000"
dead = set(deadends)
if start in dead:
return -1
visited = set()
queue = []
queue.append(start)
visited.add(start)
level = 0
while queue:
level += 1
size = len(queue)
for i in range(size):
curt = queue.pop(0)
for next in self.getnexts(curt):
if target == next:
return level
if next not in visited and next not in dead:
queue.append(next)
visited.add(next)
return -1
def getnexts(self, s):
for i in range(4):
yield s[:i] + str((int(s[i]) + 1) % 10) + s[i+1:]
yield s[:i] + str((int(s[i]) - 1) % 10) + s[i+1:]Check on curt get TLE, however check both on curt and next should work.
Map<Integer, Integer> map;
public int confusingNumberII(int N) {
map = new HashMap<>();
map.put(0, 0);
map.put(1, 1);
map.put(6, 9);
map.put(8, 8);
map.put(9, 6);
Queue<Integer> q = new LinkedList<>();
q.offer(0);
int count = 0;
Set<Integer> set = new HashSet<>();
set.add(0);
while (!q.isEmpty()) {
int curt = q.poll();
for (int d : map.keySet()) {
int next = curt * 10 + d;
if (next > N) return count;
if (next != 0) {
q.offer(next);
}
if (isConfusing(next) && !set.contains(next)) {
set.add(next);
count++;
}
}
}
return count;
}
private boolean isConfusing(int n) {
long rot = 0;
int tmp = n;
while (n > 0) {
rot = rot * 10 + map.get(n % 10);
n /= 10;
}
return rot != tmp;
} Map<Integer, Integer> map;
public int confusingNumberII(int N) {
map = new HashMap<>();
map.put(0, 0);
map.put(1, 1);
map.put(6, 9);
map.put(8, 8);
map.put(9, 6);
Queue<Integer> q = new LinkedList<>();
q.offer(0);
int count = 0;
Set<Integer> set = new HashSet<>();
while (!q.isEmpty()) {
int curt = q.poll();
if (curt > N) break;
if (isConfusing(curt) && !set.contains(curt)) {
set.add(curt);
count++;
}
for (int d : map.keySet()) {
q.offer(curt * 10 + d);
}
}
return count;
}
private boolean isConfusing(int n) {
long rot = 0;
int tmp = n;
while (n > 0) {
rot = rot * 10 + map.get(n % 10);
n /= 10;
}
return rot != tmp;
} public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
int[][] graph = new int[n][n];
buildGraph(graph, n, red_edges, blue_edges);
Queue<int[]> q = new LinkedList<>();
Set<String> set = new HashSet<>();
q.offer(new int[]{0, 1});
q.offer(new int[]{0, -1});
int[] res = new int[n];
Arrays.fill(res, Integer.MAX_VALUE);
res[0] = 0;
int level = 0;
while (!q.isEmpty()) {
level++;
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curt = q.poll();
int node = curt[0], color = curt[1];
for (int k = 0; k < n; k++) {
if (graph[node][k] == 0 || graph[node][k] == -color) {
if (!set.add(k + " " + (-color))) continue;
q.offer(new int[]{k, -color});
res[k] = Math.min(res[k], level);
}
}
}
}
for (int i = 1; i < n; i++) {
if (res[i] == Integer.MAX_VALUE) {
res[i] = -1;
}
}
return res;
}
private void buildGraph(int[][] g, int n, int[][] red_edges, int[][] blue_edges) {
for (int i = 0; i < n; i++) {
Arrays.fill(g[i], -n);
}
for (int[] e : red_edges) {
g[e[0]][e[1]] = 1;
}
for (int[] e : blue_edges) {
int from = e[0];
int to = e[1];
if (g[from][to] == 1) {
g[from][to] = 0;
} else {
g[from][to] = -1;
}
}
}bfs level order traverse starts from all buildings, go through all each empty grids, to calculate the cumulated shortest distance from all buildings. Also count how many houses can reach this spot, when output, detect if this spot can be reached by all starting points.
T: O((mn)^2) .S: O(mn)
int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n], count = new int[m][n];
int house = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
house++;
dist[i][j] = -1;
bfs(grid, dist, count, i, j);
} else if (grid[i][j] == 2) {
dist[i][j] = -1;
}
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] != -1 && grid[i][j] == 0 && count[i][j] == house) {
min = Math.min(min, dist[i][j]);
}
}
}
return min == Integer.MAX_VALUE ? -1 : min;
}
private void bfs(int[][] grid, int[][] dist, int[][] count, int x, int y) {
int n = grid[0].length;
Set<Integer> set = new HashSet<>();
Queue<int[]> q = new LinkedList<>();
set.add(x * n + y);
q.offer(new int[]{x, y});
int level = 0;
while (!q.isEmpty()) {
level++;
int size = q.size();
for (int k = 0; k < size; k++) {
int[] curt = q.poll();
for (int[] d : direction) {
int nx = curt[0] + d[0];
int ny = curt[1] + d[1];
if (inbound(nx, ny, grid)
&& !set.contains(nx * n + ny)
&& grid[nx][ny] != 1
&& grid[nx][ny] != 2) {
count[nx][ny]++;
dist[nx][ny] += level;
set.add(nx * n + ny);
q.offer(new int[]{nx, ny});
}
}
}
}
}
private boolean inbound(int x, int y, int[][] grid) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
} int x = -1, y = -1;
int max = -1;
int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
public int shortestPathAllKeys(String[] grid) {
int m = grid.length, n = grid[0].length();
char[][] g = new char[m][n];
for (int i = 0; i < grid.length; i++) {
g[i] = grid[i].toCharArray();
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '@') {
x = i;
y = j;
} else if (g[i][j] >= 'a' && g[i][j] <= 'z') {
max = Math.max(g[i][j] - 'a' + 1, max);
}
}
}
Queue<Node> q = new LinkedList<>();
Set<String> set = new HashSet<>();
set.add(0 + " " + x + " " + y);
q.offer(new Node(x, y, 0));
int level = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Node curt = q.poll();
if (curt.keys == Math.pow(2, max) - 1) {
return level;
}
for (int[] d : direction) {
int nx = curt.x + d[0];
int ny = curt.y + d[1];
int keys = curt.keys;
if (inbound(g, nx, ny)) {
if (g[nx][ny] == '#') continue;
if (g[nx][ny] >= 'a' && g[nx][ny] <= 'z') {
keys |= 1 << g[nx][ny] - 'a';
}
if (g[nx][ny] >= 'A' && g[nx][ny] <= 'Z' && ((keys >> (g[nx][ny] - 'A')) & 1) == 0) {
continue;
}
if (!set.contains(keys + " " + nx + " " + ny)) {
set.add(keys + " " + nx + " " + ny);
q.offer(new Node(nx, ny, keys));
}
}
}
}
level++;
}
return -1;
}
class Node {
int x, y, keys;
public Node(int x, int y, int keys) {
this.x = x;
this.y = y;
this.keys = keys;
}
}
private boolean inbound(char[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
} public int slidingPuzzle(int[][] board) {
StringBuilder start = new StringBuilder();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) start.append(board[i][j]);
}
int[][] nexts = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
String target = "123450";
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
visited.add(start.toString());
q.offer(start.toString());
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String curt = q.poll();
if (curt.equals(target)) return step;
int zero = curt.indexOf('0');
if (zero == -1) return -1;
for (int next : nexts[zero]) {
StringBuilder sb = new StringBuilder(curt);
char temp = sb.charAt(next);
sb.setCharAt(zero, temp);
sb.setCharAt(next, '0');
String n = sb.toString();
if (n.equals(target)) return step + 1;
if (visited.contains(n)) continue;
q.offer(n);
visited.add(n);
}
}
step++;
}
return -1;
} int[][] move = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
public int slidingPuzzle(int[][] board) {
String target = "123450";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
sb.append(board[i][j]);
}
}
String start = sb.toString();
if (start.equals(target)) {
return 0;
}
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
int level = 0;
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0; i < size; i++) {
String curt = queue.poll();
for (String next : getNext(curt)) {
if (next.equals(target)) {
return level;
}
if (!visited.contains(next)) {
queue.offer(next);
visited.add(next);
}
}
}
}
return -1;
}
private Set<String> getNext(String s) {
Set<String> set = new HashSet<>();
StringBuilder sb = new StringBuilder(s);
int u = s.indexOf("0");
char uchar = sb.charAt(u);
for (int v : move[u]) {
char vchar = sb.charAt(v);
sb.setCharAt(v, uchar);
sb.setCharAt(u, vchar);
set.add(sb.toString());
System.out.println(sb.toString());
sb = new StringBuilder(s);
}
return set;
}public int shortestPath(int[][] grid, int k) {
int step = 0;
int m = grid.length;
int n = grid[0].length;
int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int[][] seen = new int[m][n]; // min obstacles elimination from (0,0) to (x, y)
for (int i = 0; i < m; i++) {
Arrays.fill(seen[i], Integer.MAX_VALUE);
}
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0, 0});
seen[0][0] = 0;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
int[] cur = q.poll();
if (cur[0] == m - 1 && cur[1] == n - 1) {
return step;
}
for (int[] dir : DIRS) {
int x = dir[0] + cur[0];
int y = dir[1] + cur[1];
if (x < 0 || x >= m || y < 0 || y >= n) {
continue;
}
int o = grid[x][y] + cur[2];
if (o >= seen[x][y] || o > k) {
continue;
}
seen[x][y] = o;
q.offer(new int[]{x, y, o});
}
}
++step;
}
return -1;
} int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int cutOffTree(List<List<Integer>> forest) {
if (forest == null || forest.size() == 0 || forest.get(0).size() == 0) {
return -1;
}
List<int[]> treeHeights = getAllTreeHights(forest);
Collections.sort(treeHeights, (a, b) -> (a[2] - b[2]));
int i = 0;
int[] pre = new int[]{0, 0};
int step = 0;
while (i < treeHeights.size()) {
int[] curt = treeHeights.get(i);
int s = getMinimumSteps(forest, pre[0], pre[1], curt[0], curt[1]);
if (s == -1) return -1;
step += s;
pre[0] = curt[0];
pre[1] = curt[1];
forest.get(pre[0]).set(pre[1], 1);
i++;
}
return step;
}
private int getMinimumSteps(List<List<Integer>> forest, int curX, int curY, int aimX, int aimY) {
int n = forest.get(0).size();
Queue<int[]> q = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
q.offer(new int[]{curX, curY});
visited.add(curX * n + curY);
int level = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curt = q.poll();
if (curt[0] == aimX && curt[1] == aimY) {
return level;
}
for (int[] d : directions) {
int nx = curt[0] + d[0];
int ny = curt[1] + d[1];
if (inbound(forest, nx, ny) && !visited.contains(nx * n + ny) && forest.get(nx).get(ny) != 0) {
visited.add(nx * n + ny);
q.offer(new int[]{nx, ny});
}
}
}
level++;
}
return -1;
}
private List<int[]> getAllTreeHights(List<List<Integer>> forest) {
List<int[]> treeHeights = new LinkedList<>();
for (int i = 0; i < forest.size(); i++) {
for (int j = 0; j < forest.get(0).size(); j++) {
int[] res = new int[3];
res[0] = i;
res[1] = j;
res[2] = forest.get(i).get(j);
if (res[2] > 1) {
treeHeights.add(res);
}
}
}
return treeHeights;
}
private boolean inbound(List<List<Integer>> forest, int x, int y) {
return x >= 0 && y >= 0 && x < forest.size() && y < forest.get(0).size();
}import collections
class Solution(object):
def cutOffTree(self, G):
"""
:type forest: List[List[int]]
:rtype: int
"""
if not G or not G[0]: return -1
m, n = len(G), len(G[0])
trees = []
for i in xrange(m):
for j in xrange(n):
if G[i][j] > 1:
trees.append((G[i][j], i, j))
trees = sorted(trees)
count = 0
cx, cy = 0, 0
for h, x, y in trees:
step = self.BFS(G, cx, cy, x, y)
if step == -1:
return -1
else:
count += step
G[x][y] = 1
cx, cy = x, y
return count
def BFS(self, G, cx, cy, tx, ty):
m, n = len(G), len(G[0])
visited = [[False for j in xrange(n)] for i in xrange(m)]
Q = collections.deque()
step = -1
Q.append((cx, cy))
while len(Q) > 0:
size = len(Q)
step += 1
for i in xrange(size):
x, y = Q.popleft()
visited[x][y] = True
if x == tx and y == ty:
return step
for nx, ny in [(x + 1, y), (x - 1, y), (x, y-1), (x, y + 1)]:
if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]:
continue
Q.append((nx, ny))
return -1BFS Level order traversal.
public int minJumps(int[] arr) {
int n = arr.length;
HashMap<Integer, List<Integer>> indicies = new HashMap<>();
for (int i = 0; i < n; i++)
indicies.computeIfAbsent(arr[i], x -> new LinkedList<>()).add(i);
boolean[] visited = new boolean[n];
Queue<Integer> q = new LinkedList<>();
q.offer(0);
int level = 0;
visited[0] = true;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int index = q.poll();
if (index == n - 1) {
return level;
}
List<Integer> nexts = indicies.get(arr[index]);
nexts.add(index + 1);
nexts.add(index - 1);
for (int next : nexts) {
if (next >= 0 && next < n && !visited[next] && next != index) {
q.offer(next);
visited[next] = true;
}
}
nexts.clear();
}
level++;
}
return -1;
}DFS
