Posts tagged as “grid”

花花酱 LeetCode 2435. Paths in Matrix Whose Sum Is Divisible by K

By zxi on October 10, 2022

You are given a 0-indexed m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right.

Return the number of paths where the sum of the elements on the path is divisible by k. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: There are two paths where the sum of the elements on the path is divisible by k.
The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.

Example 2:

Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.

Example 3:

Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 5 * 10⁴
1 <= m * n <= 5 * 10⁴
0 <= grid[i][j] <= 100
1 <= k <= 50

Solution: DP

Let dp[i][j][r] := # of paths from (0,0) to (i,j) with path sum % k == r.

init: dp[0][0][grid[0][0] % k] = 1

dp[i][j][(r + grid[i][j]) % k] = dp[i-1][j][r] + dp[i][j-1][r]

ans = dp[m-1][n-1][0]

Time complexity: O(m*n*k)
Space complexity: O(m*n*k) -> O(n*k)

C++

// Author: Huahua

class Solution {

public:

int numberOfPaths(vector<vector<int>>& grid, int k) {

const int kMod = 1e9 + 7;

const int m = grid.size();

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

vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k)));

dp[0][0][grid[0][0] % k] = 1;

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

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

if (i == 0 && j == 0) continue;

for (int r = 0; r < k; ++r)

dp[i][j][(r + grid[i][j]) % k] =

((j ? dp[i][j - 1][r] : 0) + (i ? dp[i - 1][j][r] : 0)) % kMod;

}

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

}

};

花花酱 LeetCode 2257. Count Unguarded Cells in the Grid

By zxi on May 1, 2022

You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the i^th guard and j^th wall respectively.

A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.

Return the number of unoccupied cells that are not guarded.

Example 1:

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.

Example 2:

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.

Constraints:

1 <= m, n <= 10⁵
2 <= m * n <= 10⁵
1 <= guards.length, walls.length <= 5 * 10⁴
2 <= guards.length + walls.length <= m * n
guards[i].length == walls[j].length == 2
0 <= row_i, row_j < m
0 <= col_i, col_j < n
All the positions in guards and walls are unique.

Solution: Simulation

Enumerate each cell, for each guard, shoot rays to 4 directions, mark cells on the way to 1 and stop when hit a guard or a wall.

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua

class Solution {

public:

int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {

vector<vector<int>> s(m, vector<int>(n));

for (const auto& g : guards)

s[g[0]][g[1]] = 2;

for (const auto& w : walls)

s[w[0]][w[1]] = 3;

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

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

if (s[i][j] != 2) continue;

for (int y = i - 1; y >= 0; s[y--][j] = 1)

if (s[y][j] >= 2) break;

for (int y = i + 1; y < m; s[y++][j] = 1)

if (s[y][j] >= 2) break;

for (int x = j - 1; x >= 0; s[i][x--] = 1)

if (s[i][x] >= 2) break;

for (int x = j + 1; x < n; s[i][x++] = 1)

if (s[i][x] >= 2) break;

}

int ans = 0;

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

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

ans += !s[i][j];

return ans;

}

};

花花酱 LeetCode 2146. K Highest Ranked Items Within a Price Range

By zxi on February 3, 2022

You are given a 0-indexed 2D integer array grid of size m x n that represents a map of the items in a shop. The integers in the grid represent the following:

0 represents a wall that you cannot pass through.
1 represents an empty cell that you can freely move to and from.
All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.

It takes 1 step to travel between adjacent grid cells.

You are also given integer arrays pricing and start where pricing = [low, high] and start = [row, col] indicates that you start at the position (row, col) and are interested only in items with a price in the range of [low, high] (inclusive). You are further given an integer k.

You are interested in the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different:

Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
Price (lower price has a higher rank, but it must be in the price range).
The row number (smaller row number has a higher rank).
The column number (smaller column number has a higher rank).

Return the k highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.

Example 1:

Input: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
Output: [[0,1],[1,1],[2,1]]
Explanation: You start at (0,0).
With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2).
The ranks of these items are:
- (0,1) with distance 1
- (1,1) with distance 2
- (2,1) with distance 3
- (2,2) with distance 4
Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).

Example 2:

Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
Output: [[2,1],[1,2]]
Explanation: You start at (2,3).
With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1).
The ranks of these items are:
- (2,1) with distance 2, price 2
- (1,2) with distance 2, price 3
- (1,1) with distance 3
- (0,1) with distance 4
Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).

Example 3:

Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
Output: [[2,1],[2,0]]
Explanation: You start at (0,0).
With a price range of [2,3], we can take items from (2,0) and (2,1). 
The ranks of these items are: 
- (2,1) with distance 5
- (2,0) with distance 6
Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). 
Note that k = 3 but there are only 2 reachable items within the price range.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
0 <= grid[i][j] <= 10⁵
pricing.length == 2
2 <= low <= high <= 10⁵
start.length == 2
0 <= row <= m - 1
0 <= col <= n - 1
grid[row][col] > 0
1 <= k <= m * n

Solution: BFS + Sorting

Use BFS to collect reachable cells and sort afterwards.

Time complexity: O(mn + KlogK) where K = # of reachable cells.

Space complexity: O(mn)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {

const int m = grid.size();

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

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

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

seen[start[0]][start[1]] = 1;

vector<vector<int>> cells;

queue<array<int, 3>> q;

q.push({start[0], start[1], 0});

while (!q.empty()) {

auto [y, x, d] = q.front(); q.pop();

if (grid[y][x] >= pricing[0] && grid[y][x] <= pricing[1])

cells.push_back({d, grid[y][x], y, x});

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

const int tx = x + dirs[i];

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

if (tx < 0 || tx >= n || ty < 0 || ty >= m

|| !grid[ty][tx] || seen[ty][tx]++) continue;

q.push({ty, tx, d + 1});

}

sort(begin(cells), end(cells), less<vector<int>>());

vector<vector<int>> ans;

for (int i = 0; i < min(k, (int)(cells.size())); ++i)

ans.push_back({cells[i][2], cells[i][3]});

return ans;

}

};

花花酱 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 529. Minesweeper

By zxi on March 9, 2020

Let’s play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over – change it to ‘X’.
If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
Return the board when no more squares will be revealed.

Example 1:

Input: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Example 2:

Input: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

Note:

The range of the input matrix’s height and width is [1,50].
The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
The input board won’t be a stage when game is over (some mines have been revealed).
For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

Solution: DFS

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {

const int m = board.size();

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

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

if (board[y][x] != 'E') return;

int c = 0;

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty)

if (tx >= 0 && tx < n && ty >= 0 && ty < m)

c += board[ty][tx] == 'M';

if (c > 0) {

board[y][x] = '0' + c;

return;

}

board[y][x] = 'B';

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty)

if (tx >= 0 && tx < n && ty >= 0 && ty < m)

dfs(tx, ty);

};

int x = click[1];

int y = click[0];

dfs(x, y);

if (board[y][x] == 'M') board[y][x] = 'X';

return board;

}

};

Solution 2: BFS

Python3

# Author: Huahua

class Solution:

def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

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

cx, cy = click[1], click[0]

q = [(cx, cy)]

while q:

q2 = []

for x, y in q:

if board[y][x] != 'E': continue

c = 0

for tx in range(x - 1, x + 2):

for ty in range(y - 1, y + 2):

if 0 <= tx < n and 0 <= ty < m and board[ty][tx] == 'M':

c += 1

if c > 0:

board[y][x] = chr(ord('0') + c)

continue

board[y][x] = 'B'

for tx in range(x - 1, x + 2):

for ty in range(y - 1, y + 2):

if 0 <= tx < n and 0 <= ty < m and board[ty][tx] == 'E':

q2.append((tx, ty))

q = q2

if board[cy][cx] == 'M': board[y][x] = 'X'

return board