TopCoder SRM 570 - 900: CurvyonRails

Problem Statement

给定一个 n * m 的棋盘，标记棋盘上的一些格为城镇，
再标记城镇中的一些为关键格。你需要铺设轨道，有以下要求：

1. 非城镇上不允许铺设轨道。
2. 每个城镇铺一段轨道，连接它的四个边界中的两个。
3. 每段轨道需要连接另外两段轨道。
注意：所有城镇不必互相连通。

不难想象，棋盘上的城镇被连接成了若干个互不相交的环。
你需要尽可能地在关键格上铺设弯轨道。
因此，对于一种合法的方案，定义它的费用为“铺设了直轨道的关键格的个数”。
判断解的存在性，在此基础上，最小化铺设轨道的费用。
约定：n,m <= 25

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.

Test cases

input
- field {"..",
  ".."}
output
Returns 0

note

It is possible to construct a round railroad that passes through all towns.
input
- field {"wCCww",
  "wCC..",
  "..w..",
  "....w",
  "ww..w"}
output
Returns 0

note

There are two valid ways to construct the railroads. In the left picture, there is one town with unhappy Curvies. In the right picture, there are no towns with unhappy Curvies.
input
- field {"C.w",
  "...",
  ".C."}
output
Returns 1

note

The curvy in the middle of the bottom row will be unhappy.
input
- field { "." }
output
Returns -1

note

There is no way to construct the railroads.
input
- field { "w" }
output
Returns 0

note

There is no town.
input
- field {"CC..CCCw.CwC..CC.w.C",
  "C.CCCwCCC.w.w..C.w..",
  "wwww...CC.wC.Cw.CC..",
  "CC..CC.w..w.C..CCCC.",
  "CC.CCC..CwwCCC.wCC..",
  "w.C..wwCC.CC.wwwCC..",
  ".CC.CC..CCC..CC.CC.C",
  "Cw....C.C.CCC...CC..",
  "CC.C..Cww.C.CwwwC..w",
  "wCCww..C...CCCCCCC.w",
  "C.CCw.CC.ww...C.CCww",
  "C.C.C.CCwCC..wCCw.Cw",
  "CCC.C...w..C.wC.wCCw",
  "CC.C..C..CCC.CC.C...",
  "C.ww...CCC..CC...CCC",
  "...CCC.CwwwC..www.C.",
  "wwCCCCC.w.C.C...wCwC",
  "CCwC.CwCCC.C.w.Cw...",
  "C.w.wC.CC.CCC.C.w.Cw",
  "CCw.CCC..C..CC.CwCCw",
  "C.wwwww.CwwCCwwwwwww"}
output
Returns 9

back to the menu

SRM 570 1 900 CurvyonRails

Problem Statement

Definition

Limits

Constraints

Test cases