Minimum Number of Visited Cells in a Grid Solution in C++

Problem Description

Imagine you’re a brave adventurer trying to navigate through a grid filled with cells that either allow you to move or are just plain obstacles. Your mission, should you choose to accept it, is to find the minimum number of cells you need to visit to reach the bottom-right corner of the grid from the top-left corner. Sounds easy, right? Well, it’s like trying to find the last piece of pizza at a party where everyone is eyeing it!

In this grid, each cell contains a number that tells you how far you can jump to the right or down. If you land on a cell with a zero, well, congratulations! You’ve just hit a dead end. So, how do you navigate this maze of cells without losing your mind?

Code Solution


class SegmentTree {
 public:
  explicit SegmentTree(int n, int kInf) : kInf(kInf), n(n), tree(4 * n, kInf) {}

  void update(int i, int val) {
    update(0, 0, n - 1, i, val);
  }

  int query(int i, int j) const {
    return query(0, 0, n - 1, i, j);
  }

 private:
  const int kInf;
  const int n;
  vector tree;

  void update(int treeIndex, int lo, int hi, int i, int val) {
    if (lo == hi) {
      tree[treeIndex] = val;
      return;
    }
    const int mid = (lo + hi) / 2;
    if (i <= mid)
      update(2 * treeIndex + 1, lo, mid, i, val);
    else
      update(2 * treeIndex + 2, mid + 1, hi, i, val);
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
  }

  int query(int treeIndex, int lo, int hi, int i, int j) const {
    if (i <= lo && hi <= j)
      return tree[treeIndex];
    if (j < lo || hi < i)
      return kInf;
    const int mid = (lo + hi) / 2;
    return merge(query(treeIndex * 2 + 1, lo, mid, i, j),
                 query(treeIndex * 2 + 2, mid + 1, hi, i, j));
  }

  int merge(int left, int right) const {
    return min(left, right);
  }
};

class Solution {
 public:
  int minimumVisitedCells(vector>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    const int kInf = (m + n) * 2 - 1;
    vector rows(m, SegmentTree(n, kInf));
    vector cols(n, SegmentTree(m, kInf));

    rows[m - 1].update(n - 1, 1);
    cols[n - 1].update(m - 1, 1);

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j) {
        if (grid[i][j] == 0)
          continue;
        const int moveRight = rows[i].query(j + 1, grid[i][j] + j);
        const int moveDown = cols[j].query(i + 1, grid[i][j] + i);
        const int minMove = min(kInf, min(moveRight, moveDown) + 1);
        rows[i].update(j, minMove);
        cols[j].update(i, minMove);
      }

    const int res = rows[0].query(0, 0);
    return res == kInf ? -1 : res;
  }
};

Approach Explanation

The solution employs a segment tree to efficiently manage and query the minimum number of cells visited. The update function modifies the segment tree when a cell is visited, while the query function retrieves the minimum number of cells needed to reach a specific cell. The algorithm iterates through the grid in reverse order, ensuring that it calculates the minimum moves required to reach the bottom-right corner from each cell.

Time and Space Complexity

Time Complexity: O(m * n * log(n)), where m is the number of rows and n is the number of columns in the grid. This is due to the segment tree operations for each cell.
Space Complexity: O(m * n), as we maintain two segment trees for rows and columns.

Real-World Example

Think of this problem like trying to navigate through a crowded mall during the holiday season. You want to get to the food court (bottom-right corner) from the entrance (top-left corner). Each store (cell) has a sign that tells you how many stores you can skip over to get to the next one. If you hit a store that’s closed (zero), you’re stuck! The goal is to find the quickest route to satisfy your hunger without getting lost in the sea of shoppers.