Bigbasket Delivery Zone Analysis
Bigbasket optimizes delivery routes by grouping houses into "delivery zones". A delivery zone is a cluster of houses that are reachable from each other, allowing a single delivery executive to cover them efficiently. However, some areas might be temporarily restricted (e.g., due to roadwork, construction) and cannot be traversed. We need to identify and count the number of independent delivery zones given a city map.
Given a 2D grid representing a city's layout, where '1' denotes a house requiring delivery, '0' denotes an empty lot, and 'R' denotes a restricted area, find the total number of distinct delivery zones. A delivery zone is defined as a group of '1's where every '1' in the group is reachable from every other '1' in the same group by only moving horizontally or vertically through other '1's or '0's. Movement through 'R' cells is strictly forbidden.
Input:
grid: A m x n array of characters, where grid[i][j] can be '1' (house), '0' (empty lot), or 'R' (restricted area).Output:
Examples
Example 1
Input:
grid = [["1","1","0","R"],["0","1","0","1"],["1","0","R","1"]]
Output:
1
Note:
All '1's are reachable from each other by traversing through '1's and '0's, avoiding 'R' cells. For instance, the house at (0,0) can reach the house at (1,3) via a path like (0,0)->(0,1)->(0,2)->(1,2)->(1,3). All houses form a single large delivery zone.
Example 2
Input:
grid = [["1","0","0"],["0","R","0"],["0","0","1"]]
Output:
1
Note:
The house at (0,0) can reach the house at (2,2) by moving through the '0' cells, navigating around the 'R' cell at (1,1). Thus, they form a single delivery zone.
Example 3
Input:
grid = [["1","1","1"],["1","1","1"],["1","1","1"]]
Output:
1
Note:
All '1's are connected and can reach each other, forming a single large delivery zone.
Constraints
m is the number of rows, n is the number of columns in the grid.1 <= m, n <= 300grid[i][j] will be either '1', '0', or 'R'.Loading editor...