Posts tagged as “shortest path”

花花酱 LeetCode 542. 01 Matrix

By zxi on July 14, 2018

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:

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

Solution 1: DP

Two passes:

down, right
up, left

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 132 ms

class Solution {

public:

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

int m = matrix.size();

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

vector<vector<int>> ans(m, vector<int>(n, INT_MAX - m * n));

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

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

if (matrix[i][j]) {

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

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

} else {

ans[i][j] = 0;

}

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

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

if (i < m - 1) ans[i][j] = min(ans[i][j], ans[i + 1][j] + 1);

if (j < n - 1) ans[i][j] = min(ans[i][j], ans[i][j + 1] + 1);

}

return ans;

}

};

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)

// Author: Huahua

// Running time: 136 ms

class Solution {

public:

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

queue<pair<int, int>> q;

vector<vector<int>> seen(m, vector<int>(n, 0));

vector<vector<int>> ans(m, vector<int>(n, INT_MAX));

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

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

if (matrix[i][j] == 0) {

q.push({i, j});

seen[i][j] = 1;

}

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

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto pair = q.front(); q.pop();

int i = pair.first;

int j = pair.second;

ans[i][j] = steps;

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

int x = j + dirs[k];

int y = i + dirs[k + 1];

if (x < 0 || x >= n || y < 0 || y >= m || seen[y][x]) continue;

seen[y][x] = 1;

q.push({y, x});

}

++steps;

}

return ans;

}

};

花花酱 LeetCode 864. Shortest Path to Get All Keys

By zxi on July 8, 2018

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 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
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)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int shortestPathAllKeys(vector<string>& grid) {

int m = grid.size();

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

int all_keys = 0;

queue<int> q;

vector<vector<vector<int>>> seen(m, vector<vector<int>>(n, vector<int>(64, 0)));

// Init

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

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

const char c = grid[i][j];

if (c == '@') {

q.push((j << 16) | (i << 8));

seen[i][j][0] = 1;

} else if (c >= 'a' && c <= 'f') {

all_keys |= (1 << (c - 'a'));

}

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

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

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

int x = s >> 16;

int y = (s >> 8) & 0xFF;

int keys = s & 0xFF;

if (keys == all_keys) return steps;

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

int nkeys = keys;

int nx = x + dirs[i];

int ny = y + dirs[i + 1];

if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

const char c = grid[ny][nx];

if (c == '#') continue; // Wall

// Do not have the key.

if (c >= 'A' && c <= 'F' && !(keys & (1 << (c - 'A')))) continue;

// Update the keys we have.

if (c >= 'a' && c <= 'f') nkeys |= (1 << (c - 'a'));

if (seen[ny][nx][nkeys]) continue;

q.push((nx << 16) | (ny << 8) | nkeys);

seen[ny][nx][nkeys] = 1;

}

++steps;

}

return -1;

}

};

Python3

# Author: Huahua, 390 ms

class Solution:

def shortestPathAllKeys(self, grid):

m, n = len(grid), len(grid[0])

all_keys = 0

seen = [[[None]* 64 for _ in range(n)] for _ in range(m)]

q = collections.deque()

for i in range(m):

for j in range(n):

c = grid[i][j]

if c == '@':

q.append((j << 16) | (i << 8))

seen[i][j][0] = 1

elif c >= 'a' and c <= 'f':

all_keys |= (1 << (ord(c) - ord('a')))

dirs = [-1, 0, 1, 0, -1]

steps = 0

while q:

size = len(q)

while size > 0:

size -= 1

s = q.popleft()

x = s >> 16

y = (s >> 8) & 0xff

keys = s & 0xff

if keys == all_keys: return steps

for i in range(4):

nx, ny, nkeys = x + dirs[i], y + dirs[i + 1], keys

if nx < 0 or nx >= n or ny < 0 or ny >= m: continue

c = grid[ny][nx]

if c == '#': continue

if c in string.ascii_uppercase and keys & (1 << (ord(c) - ord('A'))) == 0: continue

if c in string.ascii_lowercase: nkeys |= (1 << (ord(c) - ord('a')))

if seen[ny][nx][nkeys]: continue

q.append((nx << 16) | (ny << 8) | nkeys)

seen[ny][nx][nkeys] = 1

steps += 1

return -1

Problem

题目大意：求顶点覆盖的最短路径。

https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Solution: BFS

Time complexity: O(n*2^n)

Space complexity: O(n*2^n)

C++

// Author: Huahua

// Running time: 34 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int kAns = (1 << (graph.size())) - 1;

queue<pair<int, int>> q;

unordered_set<int> visited; // (cur_node << 16) | state

for (int i = 0; i < graph.size(); ++i)

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int n = p.first;

int state = p.second;

if (state == kAns) return steps;

int key = (n << 16) | state;

if (visited.count(key)) continue;

visited.insert(key);

for (int next : graph[n])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

C++ / vector

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int n = graph.size();

const int kAns = (1 << n) - 1;

queue<pair<int, int>> q;

vector<vector<int>> visited(n, vector<int>(1 << n));

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

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int node = p.first;

int state = p.second;

if (state == kAns) return steps;

if (visited[node][state]) continue;

visited[node][state] = 1;

for (int next : graph[node])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

Problem

题目大意：给你每辆公交车的环形路线，问最少需要坐多少辆公交车才能送S到达T。

https://leetcode.com/problems/bus-routes/description/

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

Solution: BFS

Time Complexity: O(m*n) m: # of buses, n: # of routes

Space complexity: O(m*n + m)

C++

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {

if (S == T) return 0;

unordered_map<int, vector<int>> m;

for (int i = 0; i < routes.size(); ++i)

for (const int stop : routes[i])

m[stop].push_back(i);

vector<int> visited(routes.size(), 0);

queue<int> q;

q.push(S);

int buses = 0;

while (!q.empty()) {

int size = q.size();

++buses;

while (size--) {

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

for (const int bus : m[curr]) {

if (visited[bus]) continue;

visited[bus] = 1;

for (int stop : routes[bus]) {

if (stop == T) return buses;

q.push(stop);

}

return -1;

}

};

花花酱 LeetCode 433. Minimum Genetic Mutation

By zxi on March 24, 2018

Problem

题目大意：给你一个基因库，问一个基因最少需要变异多少次才能变为另外一个基因。每次变异只能修改一个字符，并且必须在基因库里。

https://leetcode.com/problems/minimum-genetic-mutation/description/

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

Solution: BFS Shortest Path

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int minMutation(string start, string end, vector<string>& bank) {

queue<string> q;

q.push(start);

unordered_set<string> visited;

visited.insert(start);

int mutations = 0;

while (!q.empty()) {

size_t size = q.size();

while (size--) {

string curr = std::move(q.front()); q.pop();

if (curr == end) return mutations;

for (const string& gene : bank) {

if (visited.count(gene) || !validMutation(curr, gene)) continue;

visited.insert(gene);

q.push(gene);

}

++mutations;

}

return -1;

}

private:

bool validMutation(const string& s1, const string& s2) {

int count = 0;

for (int i = 0; i < s1.length(); ++i)

if (s1[i] != s2[i] && count++) return false;

return true;

}

};

Posts tagged as “shortest path”

花花酱 LeetCode 542. 01 Matrix

Problem

Solution 1: DP

Solution 2: BFS

花花酱 LeetCode 864. Shortest Path to Get All Keys

Problem

Solution: BFS

C++

Python3

Related Problems

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

Problem

Solution: BFS

Related Problems

花花酱 LeetCode 815. Bus Routes

Problem

Solution: BFS

花花酱 LeetCode 433. Minimum Genetic Mutation

Problem

Solution: BFS Shortest Path