Posts tagged as “BFS”

花花酱 LeetCode 1298. Maximum Candies You Can Get from Boxes

By zxi on December 28, 2019

Given n boxes, each box is given in the format [status, candies, keys, containedBoxes] where:

status[i]: an integer which is 1 if box[i] is open and 0 if box[i] is closed.
candies[i]: an integer representing the number of candies in box[i].
keys[i]: an array contains the indices of the boxes you can open with the key in box[i].
containedBoxes[i]: an array contains the indices of the boxes found in box[i].

You will start with some boxes given in initialBoxes array. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.

Return the maximum number of candies you can get following the rules above.

Example 1:

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2. Box 1 is closed and you don't have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

Example 2:

Input: status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
Output: 6
Explanation: You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys. The total number of candies will be 6.

Example 3:

Input: status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]
Output: 1

Example 4:

Input: status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []
Output: 0

Example 5:

Input: status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
Output: 7

Constraints:

1 <= status.length <= 1000
status.length == candies.length == keys.length == containedBoxes.length == n
status[i] is 0 or 1.
1 <= candies[i] <= 1000
0 <= keys[i].length <= status.length
0 <= keys[i][j] < status.length
All values in keys[i] are unique.
0 <= containedBoxes[i].length <= status.length
0 <= containedBoxes[i][j] < status.length
All values in containedBoxes[i] are unique.
Each box is contained in one box at most.
0 <= initialBoxes.length <= status.length
0 <= initialBoxes[i] < status.length

Solution: BFS

Only push boxes that we can open into the queue.

When can we open the box?
1. When we find it and have the key in hand.
2. When we find the key and have the box in hand.

Time complexity: O(B + K)
Space complexity: O(B)

C++

// Author: Huahua

class Solution {

public:

int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {

vector<int> found(status.size());

vector<int> hasKeys(status);

queue<int> q;

for (int b : initialBoxes) {

found[b] = 1;

if (hasKeys[b]) q.push(b);

}

int ans = 0;

while (!q.empty()) {

int b = q.front();

q.pop();

ans += candies[b];

for (int t : containedBoxes[b]) {

found[t] = 1;

if (hasKeys[t]) q.push(t);

}

for (int t : keys[b]) {

if (!hasKeys[t] && found[t]) q.push(t);

hasKeys[t] = 1;

}

return ans;

}

};

花花酱 LeetCode 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

By zxi on December 8, 2019

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

Binary matrix is a matrix with all cells equal to 0 or 1 only.

Zero matrix is a matrix with all cells equal to 0.

Example 1:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2:

Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.

Example 3:

Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6

Example 4:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix

Constraints:

m == mat.length
n == mat[0].length
1 <= m <= 3
1 <= n <= 3
mat[i][j] is 0 or 1.

Solution: BFS + bitmask

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

C++

// Author: Huahua

class Solution {

public:

int minFlips(vector<vector<int>>& mat) {

const int m = mat.size();

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

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

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

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

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

s ^= (1 << ty * n + tx);

}

return s;

};

int steps = 0;

queue<int> q;

vector<int> seen(1 << (n * m));

int start = 0;

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

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

start |= (mat[y][x] << (y * n + x));

q.push(start);

seen[start] = 1;

while (!q.empty()) {

int size = q.size();

while (size--) {

int s = q.front();

if (s == 0) return steps;

q.pop();

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

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

int t = flip(s, x, y);

if (seen[t]) continue;

seen[t] = 1;

q.push(t);

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1263. Minimum Moves to Move a Box to Their Target Location

By zxi on November 26, 2019

Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.

The game is represented by a grid of size n*m, where each element is a wall, floor, or a box.

Your task is move the box 'B' to the target position 'T' under the following rules:

Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
Floor is represented by character '.' that means free cell to walk.
Wall is represented by character '#' that means obstacle (impossible to walk there).
There is only one box 'B' and one target cell 'T' in the grid.
The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
The player cannot walk through the box.

Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

Example 1:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.

Example 2:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:

Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

Constraints:

1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid contains only characters '.', '#', 'S' , 'T', or 'B'.
There is only one character 'S', 'B' and 'T' in the grid.

Solution: BFS + DFS

BFS to search by push steps to find miminal number of pushes. Each time we move from the previous position (initial position or last push position) to a new push position. Use DFS to check that whether that path exist or not.

C++

// Author: Huahua

struct Node {

int bx;

int by;

int px;

int py;

int key() const { return ((by * 20 + bx) << 16) | (py * 20 + px); }

};

class Solution {

public:

int minPushBox(vector<vector<char>>& grid) {

const int n = grid.size();

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

Node start;

Node end;

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

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

if (grid[y][x] == 'B') {

start.bx = x;

start.by = y;

} else if (grid[y][x] == 'S') {

start.px = x;

start.py = y;

} else if (grid[y][x] == 'T') {

end.bx = x;

end.by = y;

}

auto hasPath = [&](const Node& cur, int tx, int ty) {

vector<int> seen(m*n);

function<bool(int, int)> dfs = [&](int x, int y) {

if (x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#')

return false;

if (x == cur.bx && y == cur.by) return false;

int key = y * m + x;

if (seen[key]) return false;

seen[key] = 1;

if (x == tx && y == ty) return true;

return dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);

};

return dfs(cur.px, cur.py);

};

auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) {

const int bx = cur.bx + dx;

const int by = cur.by + dy;

if (bx < 0 || bx >= m || by < 0 || by >= n || grid[by][bx] == '#')

return false;

if (!hasPath(cur, cur.bx - dx, cur.by - dy)) return false;

nxt->bx = bx;

nxt->by = by;

nxt->px = cur.bx;

nxt->py = cur.by;

return true;

};

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

unordered_set<int> seen;

queue<Node> q;

q.push(start);

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

Node cur = q.front();

q.pop();

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

Node nxt;

if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) ||

seen.count(nxt.key()))

continue;

if (nxt.bx == end.bx && nxt.by == end.by) return steps + 1;

seen.insert(nxt.key());

q.push(nxt);

}

++steps;

}

return -1;

}

};

**Solution: A* + BFS**

g : history = # of pushes
h: heuristics = Manhattan distance from the current box position to the target position, always <= actual moves.
f = g + h

C++

100

101

// Author: Huahua, 4 ms, 17.5 MB

struct Node {

int bx;

int by;

int px;

int py;

int h;

int g;

int key() const {

return ((by * m + bx) << 2) | ((bx - px) + 1) | ((by - py) + 1) >> 1;

}

int f() const { return g + h; }

bool operator< (const Node& o) const {

return f() > o.f();

}

static int m;

};

int Node::m;

class Solution {

public:

int minPushBox(vector<vector<char>>& grid) {

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

const int n = grid.size();

const int m = Node::m = grid[0].size();

Node start;

Node end;

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

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

if (grid[y][x] == 'B') {

start.bx = x;

start.by = y;

} else if (grid[y][x] == 'S') {

start.px = x;

start.py = y;

} else if (grid[y][x] == 'T') {

end.bx = x;

end.by = y;

}

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

return !(x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#');

};

auto hasPath = [&](const Node& cur, int tx, int ty) {

if (!isValid(tx, ty)) return false;

vector<int> seen(m*n);

queue<int> q;

q.push(cur.py * m + cur.px);

seen[cur.py * m + cur.px] = 1;

while (q.size()) {

int x = q.front() % m;

int y = q.front() / m;

q.pop();

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

int nx = x + dirs[i];

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

if (!isValid(nx, ny)) continue;

if (nx == cur.bx && ny == cur.by) continue;

if (nx == tx && ny == ty) return true;

if (seen[ny * m + nx]++) continue;

q.push(ny * m + nx);

}

return false;

};

auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) {

nxt->bx = cur.bx + dx;

nxt->by = cur.by + dy;

nxt->px = cur.bx;

nxt->py = cur.by;

nxt->g = cur.g + 1;

nxt->h = abs(nxt->bx - end.bx) + abs(nxt->by - end.by);

if (!isValid(nxt->bx, nxt->by)) return false;

return hasPath(cur, cur.bx - dx, cur.by - dy);

};

vector<int> seen(m*n*4);

priority_queue<Node> q;

start.g = 0;

start.h = abs(start.bx - end.bx) + abs(start.by - end.by);

q.push(start);

while (q.size()) {

Node cur = q.top();

q.pop();

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

Node nxt;

if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) || seen[nxt.key()]++) continue;

if (nxt.bx == end.bx && nxt.by == end.by) return nxt.g;

q.push(nxt);

}

return -1;

}

};

花花酱 LeetCode 1210. Minimum Moves to Reach Target with Rotations

By zxi on September 29, 2019

In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).

In one move the snake can:

Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Rotate clockwise if it’s in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).
Rotate counterclockwise if it’s in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return -1.

Example 1:

Input: grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:

Input: grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
Output: 9

Constraints:

2 <= n <= 100
0 <= grid[i][j] <= 1
It is guaranteed that the snake starts at empty cells.

Solution1: BFS

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

C++

// Author: Huahua, 48 ms, 18.1 MB

class Solution {

public:

inline int pos(int x, int y) {

return y * 100 + x;

}

inline int encode(int p1, int p2) {

return (p1 << 16) | p2;

}

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

int n = grid.size();

queue<pair<int, int>> q;

unordered_set<int> seen;

q.push({pos(0, 0), pos(1, 0)}); // tail, head

seen.insert(encode(pos(0, 0), pos(1, 0)));

int steps = 0;

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

bool v = x >= 0 && x < n && y >= 0 && y < n && !grid[y][x];

return v;

};

while (!q.empty()) {

int size = q.size();

while (size--) {

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

int y0 = p.first / 100;

int x0 = p.first % 100;

int y1 = p.second / 100;

int x1 = p.second % 100;

if (x0 == n - 2 && y0 == n - 1 &&

x1 == n - 1 && y1 == n - 1) {

return steps;

}

bool h = y0 == y1;

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

int tx0 = x0;

int ty0 = y0;

int tx1 = x1;

int ty1 = y1;

int rx = x0;

int ry = y0;

switch (i) {

case 0: // down

++ty0;

++ty1;

break;

case 1: // right

++tx0;

++tx1;

break;

case 2: // rotate

++rx;

++ry;

if (h) { // clockwise

--tx1;

++ty1;

} else { // counterclockwise

++tx1;

--ty1;

}

break;

}

if (!valid(tx0, ty0) || !valid(tx1, ty1) || !valid(rx, ry)) continue;

int key = encode(pos(tx0, ty0), pos(tx1, ty1));

if (seen.count(key)) continue;

seen.insert(key);

q.push({pos(tx0, ty0), pos(tx1, ty1)});

}

++steps;

}

return -1;

}

};

Solution 2: DP

dp[i][j].first = min steps to reach i,j (tail pos) facing right
dp[i][j].second = min steps to reach i, j (tail pos) facing down
ans = dp[n][n-1].first

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

C++

// Author: Huahua, 16 ms, 12.1MB

class Solution {

public:

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

constexpr int kInf = 1e9;

const int n = grid.size();

vector<vector<pair<int, int>>> dp(n + 1,

vector<pair<int, int>>(n + 1, {kInf, kInf}));

dp[0][1].first = dp[1][0].first = -1;

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

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

bool h = false;

bool v = false;

if (!grid[i - 1][j - 1] && j < n && !grid[i - 1][j]) {

dp[i][j].first = min(dp[i - 1][j].first, dp[i][j - 1].first) + 1;

h = true;

}

if (!grid[i - 1][j - 1] && i < n && !grid[i][j - 1]) {

dp[i][j].second = min(dp[i - 1][j].second, dp[i][j - 1].second) + 1;

v = true;

}

if (v && j < n && !grid[i][j])

dp[i][j].second = min(dp[i][j].second, dp[i][j].first + 1);

if (h && i < n && !grid[i][j])

dp[i][j].first = min(dp[i][j].first, dp[i][j].second + 1);

}

return dp[n][n - 1].first >= kInf ? -1 : dp[n][n - 1].first;

}

};

花花酱 LeetCode 1162. As Far from Land as Possible

By zxi on August 17, 2019

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1)is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

Solution: BFS

Put all land cells into a queue as source nodes and BFS for water cells, the last expanded one will be the farthest.

Time compleixty: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua, 48 ms, 13.4 MB

class Solution {

public:

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

const int n = grid.size();

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

int ans = -1;

queue<int> q; // y*100 + x

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

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

if (grid[i][j] == 1) q.push(i * 100 + j);

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

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

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

int x = p % 100;

int y = p / 100;

if (grid[y][x] == 2)

ans = max(ans, steps);

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

int tx = x + dirs[i];

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

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

grid[ty][tx] = 2;

q.push(ty * 100 + tx);

}

++steps;

}

return ans;

}

};