A repair truck must travel from Riverton to Lakeside through a rectangular network of road sections.

Each road section is either clear or damaged. The truck can use a clear section immediately. A damaged section must be repaired before the truck can use it, and each repair costs one unit.

Riverton is beside the top-left section (0,0) of the map, while Lakeside is beside the bottom-right section (rows-1, columns-1). Find the minimum number of road repairs needed to travel between the cities.

Road Map Representation

The road network is provided as a List<String>. Each string represents one row and contains comma-separated road conditions:

• C represents a clear road section.
• D represents a damaged road section.

Class

CityRoadPlanner

Constructor

CityRoadPlanner

CityRoadPlanner()

• Creates a new city road planner.

Method

findMinimumRepairs

public int findMinimumRepairs(List<String> roadMap)

• roadMap contains the road sections in top-to-bottom order.
• Returns the minimum number of damaged road sections that must be repaired to reach Lakeside.

Rules

• The truck starts on the top-left road section.
• The destination is the bottom-right road section.
• The truck may move one section up, down, left, or right.
• The truck may not move diagonally or leave the road map.
• Using a clear road section costs nothing.
• Using a damaged road section requires one repair.
• A repaired road section remains clear.
• The supplied road map must not be modified.

Constraints

• rows = roadMap.size()
• Every row contains exactly columns road sections.
• 1 ≤ rows, columns ≤ 100,000
• 2 ≤ rows * columns ≤ 100,000
• Every road section is either C or D.
• The top-left and bottom-right road sections are clear.

Examples

Example 1

findMinimumRepairs(roadMap = List.of("C,D,C,C,D", "D,D,C,D,C", "C,C,D,D,C", "D,C,C,D,C"))

Output: 2

The truck can repair one section near Riverton, follow the clear southern roads, and repair one more section before reaching Lakeside.

Example 2

findMinimumRepairs(roadMap = List.of("C,C,D,D", "D,C,D,C", "D,C,C,C", "D,D,D,C"))

Output: 0

A route made entirely of clear road sections already connects the two cities.

Example 3

findMinimumRepairs(roadMap = List.of("C,D", "D,C"))

Output: 1

Both possible routes contain one damaged section, so exactly one repair is necessary.