Posts tagged as “BFS”

花花酱 LeetCode 1391. Check if There is a Valid Path in a Grid

By zxi on March 22, 2020

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

Solution: BFS

Need to check both sides (x, y) -> (tx, ty) and (tx, ty) -> (x, y) to make sure a path exist.

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

bool hasValidPath(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<int> dirs{0, -1, 0, 1, 0}; // [up, left, down, right]

vector<set<int>> rules{

{1, 3}, {0, 2}, {1, 2},

{2, 3}, {0, 1}, {0, 3}};

queue<int> q{{0}};

vector<int> seen(m * n);

seen[0] = 1;

while (!q.empty()) {

int cx = q.front() % n;

int cy = q.front() / n;

q.pop();

if (cx == n - 1 && cy == m - 1) return true;

for (int d : rules[grid[cy][cx] - 1]) {

int x = cx + dirs[d];

int y = cy + dirs[d + 1];

int key = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || seen[key]

|| !rules[grid[y][x] - 1].count((d + 2) % 4)) continue;

seen[key] = 1;

q.push(key);

}

return false;

}

};

花花酱 LeetCode 1377. Frog Position After T Seconds

By zxi on March 8, 2020

Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from the vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [from_i, to_i] means that exists an edge connecting directly the vertices from_i and to_i.

Return the probability that after t seconds the frog is on the vertex target.

Example 1:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666 
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.

Example 2:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.

Example 3:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666

Constraints:

1 <= n <= 100
edges.length == n-1
edges[i].length == 2
1 <= edges[i][0], edges[i][1] <= n
1 <= t <= 50
1 <= target <= n
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: BFS

key: if a node has children, the fog jumps to to children so the probability at current node will become 0.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {

vector<double> p(n + 1);

p[1] = 1.0;

vector<vector<int>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n + 1);

seen[1] = 1;

queue<int> q{{1}};

while (t--) {

int size = q.size();

while (size--) {

int cur = q.front(); q.pop();

int children = 0;

for (int nxt : g[cur])

if (!seen[nxt]) ++children;

for (int nxt : g[cur])

if (!seen[nxt]++) {

q.push(nxt);

p[nxt] += p[cur] / children;

}

// key: fog jumps this node has children

if (children > 0) p[cur] = 0.0;

}

return p[target];

}

};

python3

class Solution:

def frogPosition(self, n: int, edges: List[List[int]],

t: int, target: int) -> float:

p = [0] + [1] + [0] * (n - 1)

seen = [False] + [True] + [False] * (n - 1)

q = [1]

g = [[] for _ in range(n + 1)]

for i, j in edges:

g[i].append(j)

g[j].append(i)

for _ in range(t):

q2 = []

for cur in q:

children = sum([not seen[nxt] for nxt in g[cur]])

for nxt in g[cur]:

if seen[nxt]: continue

seen[nxt] = True

q2.append(nxt)

p[nxt] = p[cur] / children

if children > 0: p[cur] = 0

q = q2

return p[target]

花花酱 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid

By zxi on February 29, 2020

Given a m x ngrid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some invalid signs on the cells of the grid which points outside the grid.

You will initially start at the upper left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path doesn’t have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1

Example 4:

Input: grid = [[2,2,2],[2,2,2]]
Output: 3

Example 5:

Input: grid = [[4]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100

Solution 1: Lazy BFS (fake DP)

dp[i][j] := min steps to reach (i, j)

Time complexity: O((m+n)*m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

auto solve = [&](int x, int y) {

int& v = dp[y][x];

if (x > 0) v = min(v, dp[y][x - 1] + (grid[y][x - 1] != 1));

if (y > 0) v = min(v, dp[y - 1][x] + (grid[y - 1][x] != 3));

if (x < n - 1) v = min(v, dp[y][x + 1] + (grid[y][x + 1] != 2));

if (y < m - 1) v = min(v, dp[y + 1][x] + (grid[y + 1][x] != 4));

};

// At most m + n steps to propagate the results to (m - 1, n -1).

for (int k = 0; k <= (m + n); ++k) {

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

solve(x, y);

for (int y = m - 1; y >= 0; --y)

for (int x = n - 1; x >= 0; --x)

solve(x, y);

}

return dp[m - 1][n - 1];

}

};

C++

// Author: Huahua, 88 ms / 22.9 MB

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2));

dp[0][0] = 0;

while (true) {

auto prev(dp);

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (grid[i - 1][j] != 3));

if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (grid[i][j - 1] != 1));

}

for (int i = m - 1; i >= 0; --i)

for (int j = n - 1; j >= 0; --j) {

if (i != m - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + (grid[i + 1][j] != 4));

if (j != n - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + (grid[i][j + 1] != 2));

}

if (prev == dp) break; // optimal solution obtained.

}

return dp[m - 1][n - 1];

}

};

Solution 2: 0-1 BFS

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

deque<pair<int, int>> q{{0, 0}};

vector<char> seen(m * n);

vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

while (!q.empty()) {

auto [p, cost] = q.front(); q.pop_front();

int x = p % n, y = p / n;

if (x == n - 1 && y == m - 1) return cost;

if (seen[p]++) continue;

for (int i = 0; i < 4; ++i) {

int tx = x + dirs[i][0], ty = y + dirs[i][1];

int tp = ty * n + tx;

if (tx < 0 || ty < 0 || tx >= n || ty >= m || seen[tp]) continue;

if (grid[y][x] == i + 1)

q.emplace_front(tp, cost);

else

q.emplace_back(tp, cost + 1);

}

return -1;

}

};

花花酱 LeetCode 1345. Jump Game IV

By zxi on February 8, 2020

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:

Input: arr = [6,1,9]
Output: 2

Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Solution: HashTable + BFS

Use a hashtable to store the indices of each unique number.

each index i has neighbors (i-1, i + 1, hashtable[arr[i]])

Use BFS to find the shortest path in this unweighted graph.

Key optimization, clear hashtable[arr[i]] after the first use, since all nodes are already on queue, no longer needed.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 124 ms, 30.5 MB

class Solution {

public:

int minJumps(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<int>> m;

for (int i = 0; i < n; ++i)

m[arr[i]].push_back(i);

vector<int> seen(n);

queue<int> q({0});

seen[0] = 1;

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int i = q.front(); q.pop();

if (i == n - 1) return steps;

if (i - 1 >= 0 && !seen[i - 1]++) q.push(i - 1);

if (i + 1 < n && !seen[i + 1]++) q.push(i + 1);

auto it = m.find(arr[i]);

if (it == m.end()) continue;

for (int nxt : it->second)

if (!seen[nxt]++) q.push(nxt);

m.erase(it); // no longer needed.

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1306. Jump Game III

By zxi on December 29, 2019

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

Solution: BFS / DFS

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool canReach(vector<int>& arr, int start) {

const int n = arr.size();

vector<int> seen(n);

seen[start] = 1;

queue<int> q;

q.push(start);

while (q.size()) {

int cur = q.front();

q.pop();

if (arr[cur] == 0) return true;

for (int i : {-1, 1}) {

int t = cur + i * arr[cur];

if (t < 0 || t >= n || seen[t]) continue;

q.push(t);

seen[t] = 1;

}

return false;

}

};

Posts tagged as “BFS”

花花酱 LeetCode 1391. Check if There is a Valid Path in a Grid

Solution: BFS

C++

花花酱 LeetCode 1377. Frog Position After T Seconds

Solution: BFS

C++

python3

花花酱 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid

Solution 1: Lazy BFS (fake DP)

C++

C++

Solution 2: 0-1 BFS

C++

花花酱 LeetCode 1345. Jump Game IV

Solution: HashTable + BFS

C++

Related Problems

花花酱 LeetCode 1306. Jump Game III

Solution: BFS / DFS

C++