275. Dasher Coverage of Connected User Areas

Dasher Coverage of Connected User Areas

You are given two binary grids representing Dasher availability and user locations. Count how many user clusters are fully covered by available Dashers.

Grid Representation

dasherAvailability represents Dasher locations.
dasherAvailability.get(row).charAt(column) == '1' means that a Dasher is available at that location.
userClusters represents user locations.
userClusters.get(row).charAt(column) == '1' means that one or more users are located at that location.
A value of '0' means that the corresponding location does not contain an available Dasher or a user.

User Cluster Rules

A user cluster consists of one or more cells containing '1' in userClusters.
Two user cells belong to the same cluster when they are connected horizontally or vertically.
Diagonally adjacent user cells are not considered connected.
A user cluster is fully covered when every cell in that cluster contains an available Dasher at the same row and column in dasherAvailability.
A cluster containing even one user cell without an available Dasher is not fully covered.

Method

Count Fully Covered User Clusters

public int countFullyCoveredUserClusters(List
         
           dasherAvailability, List
          
            userClusters)

dasherAvailability contains the Dasher availability grid, with each string representing one row.
userClusters contains the user location grid, with each string representing one row.
Return the number of user clusters that are fully covered by available Dashers.

Constraints

1 ≤ dasherAvailability.size() ≤ 500
dasherAvailability.size() == userClusters.size()
1 ≤ dasherAvailability.get(row).length() ≤ 500
Every string in both lists has the same length.
Every string contains only '0' and '1'.
The two grids have exactly the same dimensions.
1 ≤ rows * columns ≤ 250,000
Connections are considered only in the up, down, left, and right directions.

Examples

Example 1

 countFullyCoveredUserClusters( dasherAvailability = List.of("11000", "10010", "00110", "00100"), userClusters = List.of("11000", "10010", "00110", "00101"))

Output: 2

There are three user clusters. The upper-left cluster and the middle cluster have Dashers at every user location. The user in the bottom-right cell does not have a Dasher at the same location, so that cluster is not fully covered.

Example 2

 countFullyCoveredUserClusters( dasherAvailability = List.of("1010", "1000", "0111"), userClusters = List.of("1110", "1000", "0111"))

Output: 1

The upper cluster is not fully covered because one of its user cells does not contain a Dasher. The lower horizontal cluster is fully covered.

Example 3

 countFullyCoveredUserClusters( dasherAvailability = List.of("111", "101", "111"), userClusters = List.of("000", "000", "000"))

Output: 0

There are no user locations, so there are no user clusters to count.