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

public int countFullyCoveredUserClusters(List<String> dasherAvailability, List<String> 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.