Cat Carol is the queen of Gridland.
Gridland is a rectangular country divided into a grid of unit square cells.
Each cell contains either a town or a wasteland.
Carol has decided to construct some railroad tracks according to the following rules:
- The cells with wasteland must not contain any railroad tracks.
- Each town cell has to contain a single segment of railroad tracks that connects two of its four sides.
- Each segment of tracks has to be connected to two other segments of tracks (one on each end).
Note that Carol does not require the entire set of tracks to be connected.
Configurations that consist of multiple disjoint loops are acceptable, too.
A Curvy is a curious animal indigenous to Gridland.
These animals love curves and hate straight things.
Some of the towns in Gridland are inhabited by Curvies.
If such a town happens to contain a straight segment of tracks (i.e., a segment that connects two opposite sides of the cell), the Curvies in the town are very unhappy.
You are given a String[] field that describes Gridland:
each character of each element of field describes one of its cells.
The meaning of individual characters follows.
- The character '.' represents a town without Curvies.
- The character 'C' represents a town with Curvies.
- The character 'w' represents a wasteland.
Compute and return the minimal number of towns with unhappy Curvies when the railroad tracks are constructed according to the above constraints.
If there is no way to construct the railroads according to the given rules, return -1 instead. |