A DashMart is a warehouse run by DoorDash that houses items found in convenience stores, grocery stores, and restaurants. You are given a city plan with open roads, blocked roads, DashMarts, and optionally customers. City planners want you to identify how far a location is from its closest DashMart. You can only travel in four directions: up, down, left, and right. Locations are given in [row, col] format.

In the follow-up version, the city plan may also contain customers. Each customer is assigned to the closest reachable DashMart. You need to find which DashMart serves the maximum number of customers.

Input Encoding

Since the method signatures use lists instead of primitive 2-D arrays, represent the city as a List<String>. Each string is one row, and cells in that row are separated by |.

Valid cell values are:

• "." = open road
• "X" = blocked road
• "D" = DashMart
• "C" = customer (follow-up only)

Example row:

"X|.|.|D|.|.|X|.|X"

Method Signatures

Part 1

List<Integer> getClosestDashMartDistances(List<String> city, List<List<Integer>> locations)

• Return a list where each value is the shortest distance from the corresponding location to its closest DashMart.
• If a location is outside the city, return -1 for that location.
• If a location is on a blocked road, return -1 for that location.
• If a location cannot reach any DashMart, return -1 for that location.
• If a location is itself a DashMart, the distance is 0.

Follow-up

List<Integer> findDashMartServingMaximumCustomers(List<String> city)

• Return a list of exactly 2 integers: [row, col].
• This returned list represents the DashMart location that serves the maximum number of customers.
• Each customer is served by the closest reachable DashMart.
• If a customer cannot reach any DashMart, ignore that customer.
• If two DashMarts are at the same minimum distance from a customer, assign that customer to the lexicographically smaller DashMart location by row, then col.
• If multiple DashMarts serve the same maximum number of customers, return the lexicographically smaller DashMart location by row, then col.
• If the city has one or more DashMarts but no customer is assigned to any DashMart, return the lexicographically smallest DashMart location by row, then col.
• If there is no DashMart in the city, return List.of(-1, -1).

Rules

• All coordinates are 0-indexed.
• You may move only in four directions: up, down, left, and right.
• You cannot move through blocked roads.
• Any cell other than "X" is traversable.
• All rows in city have the same number of cells.

Constraints

• 1 ≤ city.size() ≤ 200
• 1 ≤ number of columns in each row ≤ 200
• 0 ≤ locations.size() ≤ 10^5
• Each location is a list of exactly 2 integers: [row, col].
• Each city cell is one of ".", "X", "D", or "C".
• There may be zero, one, or multiple DashMarts.
• The answer for each location depends only on shortest path distance over valid traversable cells.

Examples

Example 1: Distance to Closest DashMart

Input

      city = List.of(
      "X|.|.|D|.|.|X|.|X",
      "X|.|X|X|.|.|.|.|X",
      ".|.|.|D|X|X|.|X|.",
      ".|.|.|D|X|X|.|X|.",
      ".|.|.|.|.|X|.|.|X",
      ".|.|.|.|X|.|.|X|X"
      )
	  

      locations = List.of(
      List.of(200, 200),
      List.of(1, 4),
      List.of(0, 3),
      List.of(5, 8),
      List.of(0, 7),
      List.of(5, 5)
      )
    

Method Call

getClosestDashMartDistances(city = city, locations = locations)

Output

List.of(-1, 2, 0, -1, 6, 9)

Explanation

• [200, 200] is outside the city, so the answer is -1.
• [1, 4] reaches the DashMart at [0, 3] in 2 steps.
• [0, 3] is already a DashMart, so the answer is 0.
• [5, 8] is a blocked road, so the answer is -1.
• [0, 7] reaches the nearest DashMart in 6 steps.
• [5, 5] reaches the nearest DashMart in 9 steps.

Example 2: DashMart Serving Maximum Customers

Input

      city = List.of(
      "D|.|C|X|C",
      ".|X|.|.|.",
      "C|.|D|.|C",
      "X|.|.|X|C"
      )
    

Method Call

findDashMartServingMaximumCustomers(city = city)

Output

List.of(2, 2)

Explanation

• The DashMart at [0, 0] serves 2 customers.
• The DashMart at [2, 2] serves 3 customers.
• So the returned location is List.of(2, 2).