# Posts tagged as “shortest path”

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

We may make the following moves:

• 'U' moves our position up one row, if the square exists;
• 'D' moves our position down one row, if the square exists;
• 'L' moves our position left one column, if the square exists;
• 'R' moves our position right one column, if the square exists;
• '!' adds the character board[r][c] at our current position (r, c) to the answer.

Return a sequence of moves that makes our answer equal to target in the minimum number of moves.  You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"


Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"


Constraints:

• 1 <= target.length <= 100
• target consists only of English lowercase letters.

## Solution: Manhattan walk

Compute the coordinates of each char, walk from (x1, y1) to (x2, y2) in Manhattan way.
Be aware of the last row, we can only walk on ‘z’, so go left and up first if needed.

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

# Problem

https://leetcode.com/problems/shortest-bridge/description/

In a given 2D binary array A, there are two islands.  (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped.  (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]
Output: 1


Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2


Example 3:

Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Note:

1. 1 <= A.length = A[0].length <= 100
2. A[i][j] == 0 or A[i][j] == 1

# Solution: DFS + BFS

1. Use DFS to find one island and color all the nodes as 2 (BLUE).
2. Use BFS to find the shortest path from any nodes with color 2 (BLUE) to any nodes with color 1 (RED).

Time complexity: O(mn)

Space complexity: O(mn)

# Problem

Starting with an undirected graph (the “original graph”) with nodes from 0 to N-1, subdivisions are made to some of the edges.

The graph is given as follows: edges[k] is a list of integer pairs (i, j, n) such that (i, j) is an edge of the original graph,

and n is the total number of new nodes on that edge.

Then, the edge (i, j) is deleted from the original graph, n new nodes (x_1, x_2, ..., x_n) are added to the original graph,

and n+1 new edges (i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j) are added to the original graph.

Now, you start at node 0 from the original graph, and in each move, you travel along one edge.

Return how many nodes you can reach in at most M moves.

Example 1:

Input: edge = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3
Output: 13
Explanation:  The nodes that are reachable in the final graph after M = 6 moves are indicated below. 

Example 2:

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4
Output: 23

Note:

1. 0 <= edges.length <= 10000
2. 0 <= edges[i][0] < edges[i][1] < N
3. There does not exist any i != j for which edges[i][0] == edges[j][0] and edges[i][1] == edges[j][1].
4. The original graph has no parallel edges.
5. 0 <= edges[i][2] <= 10000
6. 0 <= M <= 10^9
7. 1 <= N <= 3000

# Solution: Dijkstra Shortest Path

Compute the shortest from 0 to rest of the nodes. Use HP to mark the maximum moves left to reach each node.

HP[u] = a, HP[v] = b, new_nodes[u][v] = c

nodes covered between a<->b = min(c, a + b)

Time complexity: O(ElogE)

Space complexity: O(E)

C++

Optimized Dijkstra (replace hashmap with vector)

Using SPFA

BFS

# Problem

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0


Output:

0 0 0
0 1 0
0 0 0


Example 2:
Input:

0 0 0
0 1 0
1 1 1


Output:

0 0 0
0 1 0
1 2 1


Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

# Solution 1: DP

Two passes:

1. down, right
2. up, left

Time complexity: O(mn)

Space complexity: O(mn)

# Solution 2: BFS

Start from all 0 cells and find shortest paths to rest of the cells.

Time complexity: O(mn)

Space complexity: O(mn)

# Problem

We are given a 2-dimensional grid"." is an empty cell, "#" is a wall, "@" is the starting point, ("a""b", …) are keys, and ("A""B", …) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.  We cannot walk outside the grid, or walk into a wall.  If we walk over a key, we pick it up.  We can’t walk over a lock unless we have the corresponding key.

For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid.  This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys.  If it’s impossible, return -1.

Example 1:

Input: ["@.a.#","###.#","b.A.B"]
Output: 8


Example 2:

Input: ["@..aA","..B#.","....b"]
Output: 6


Note:

1. 1 <= grid.length <= 30
2. 1 <= grid[0].length <= 30
3. grid[i][j] contains only '.''#''@''a'-'f' and 'A'-'F'
4. The number of keys is in [1, 6].  Each key has a different letter and opens exactly one lock.

# Solution: BFS

Time complexity: O(m*n*64)

Space complexity: O(m*n*64)

# Related Problems

Mission News Theme by Compete Themes.