Minimum Number of Visited Cells in a Grid

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from sortedcontainers import SortedList
from collections import deque

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        numRows, numCols = len(grid), len(grid[0])
        unvisitedColsPerRow = [SortedList(range(numCols)) for _ in range(numRows)]
        unvisitedRowsPerCol = [SortedList(range(numRows)) for _ in range(numCols)]
        cellsQueue = deque([(0, 0, 1)]) # (current row, current column, cells visited so far)

        while cellsQueue:
            currentRow, currentCol, cellsVisited = cellsQueue.popleft()
            if (currentRow, currentCol) == (numRows-1, numCols-1):
                return cellsVisited
            for nextCol in list(unvisitedColsPerRow[currentRow].irange(currentCol+1, min(currentCol+1+grid[currentRow][currentCol], numCols) - 1)):
                cellsQueue.append((currentRow, nextCol, cellsVisited+1))
                unvisitedColsPerRow[currentRow].remove(nextCol)
                unvisitedRowsPerCol[nextCol].remove(currentRow)
            for nextRow in list(unvisitedRowsPerCol[currentCol].irange(currentRow+1, min(currentRow+1+grid[currentRow][currentCol], numRows) - 1)):
                cellsQueue.append((nextRow, currentCol, cellsVisited+1))
                unvisitedRowsPerCol[currentCol].remove(nextRow)
                unvisitedColsPerRow[nextRow].remove(currentCol)
        return -1

10 Prerequisite LeetCode Problems

“2617. Minimum Number of Visited Cells in a Grid” seems to be a problem dealing with grid traversal and breadth-first search (BFS) or depth-first search (DFS). Here are 10 problems as preparation:

  1. 200. Number of Islands: This is a classic problem that requires counting the number of disconnected components in a grid, which can be solved via DFS or BFS.

  2. 695. Max Area of Island: Similar to the previous problem, but instead of counting the number of islands, you’re finding the size of the largest one.

  3. 994. Rotting Oranges: This problem requires a BFS traversal from multiple starting points.

  4. 1091. Shortest Path in Binary Matrix: This problem asks for the shortest path in a grid, which can be found using BFS.

  5. 1293. Shortest Path in a Grid with Obstacles Elimination: This problem extends the idea of finding the shortest path in a grid, but now with obstacles.

  6. 785. Is Graph Bipartite?: This problem asks you to perform BFS or DFS on a graph and checks for a certain property (bipartiteness).

  7. 130. Surrounded Regions: This problem asks you to identify all regions in the grid that are surrounded.

  8. 542. 01 Matrix: In this problem, you’re required to find the shortest distance to a target in a grid, which is a basic application of BFS.

  9. 127. Word Ladder: This problem is a bit different, as it models the problem as a graph, where BFS can be used to find the shortest transformation sequence.

  10. 279. Perfect Squares: This problem can be solved using BFS by considering each sum as a node in a graph.

These cover BFS and DFS applied to grid-based problems, should be helpful preparation for tackling “2617. Minimum Number of Visited Cells in a Grid”.

You are given a 0-indexed m x n integer matrix grid. Your initial position is at the top-left cell (0, 0).

Starting from the cell (i, j), you can move to one of the following cells:

Cells (i, k) with j < k <= grid[i][j] + j (rightward movement), or Cells (k, j) with i < k <= grid[i][j] + i (downward movement). Return the minimum number of cells you need to visit to reach the bottom-right cell (m - 1, n - 1). If there is no valid path, return -1.

Example 1:

Input: grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]] Output: 4 Explanation: The image above shows one of the paths that visits exactly 4 cells.

Example 2:

Input: grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]] Output: 3 Explanation: The image above shows one of the paths that visits exactly 3 cells.

Example 3:

Input: grid = [[2,1,0],[1,0,0]] Output: -1 Explanation: It can be proven that no path exists.

Constraints:

m == grid.length n == grid[i].length 1 <= m, n <= 105 1 <= m * n <= 105 0 <= grid[i][j] < m * n grid[m - 1][n - 1] == 0