Connection Status:
Competition Arena > Tunnels

Tunnels

SRM 574 · 2012-12-13 · by gojira_tc

SRM 574 · 2012-12-13 · by gojira_tc · Dynamic Programming, Greedy, String Manipulation
Class Name: Tunnels
Return Type: int
Method Name: minimumTunnels
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Preparing for the End of The World on 21.12.2012, Manao and his neighbours decided to dig several tunnels under their neighbourhood. All of the houses in Manao's neighbourhood are standing in a line and all of the tunnels are dug directly under them, so we can consider the neighbourhood's underground in two-dimensional space.



The underground is divided into squares 1 meter long. Each tunnel is a sequence of squares obeying the following rules:
  • Each pair of consecutive squares shares an edge.
  • No pair of non-consecutive squares shares an edge.
  • The first square in the sequence is right under the ground level.
  • If the squares are traversed from the first one to the last one, the direction in each pair will be either down, left or right. That is, a tunnel cannot contain an ascending fragment.

Note that each tunnel may have multiple squares directly below the ground level. It is also known that no two tunnels in the neighbourhood share a square and there are no two neighbouring square which belong to different tunnels. See the following examples of incorrectly built tunnel systems: in the first one, the tunnel does not begin right under the ground level; in the second one, a tunnel has an ascending fragment, in the third one, there are non-consecutive squares sharing an edge and in the fourth one, two tunnels have neighbouring squares. 

**********GROUND**********
...   X...   X..   X....X
.X.   X...   XXX   XXXXXX
...   X.X.   .XX   ..XX..
...   XXX.   ...   ..X...

Suppose we have encoded the whole underground and have an infinite grid where each cell is either 'X', denoting a dug square, or '.', denoting an undug square. You are given some rectangular fragment of this infinite grid as String[] frame. It is guaranteed that the tunnels were built according to the given rules. Return the minimum possible number of tunnels in this underground.

Constraints

  • frame will contain between 1 and 50 elements, inclusive.
  • Each element of frame will be between 1 and 50 characters long, inclusive.
  • The elements of frame will be of equal length.
  • Each character in frame will be either '.' or 'X'.
  • The picture given by frame will be a fragment of a correct tunnels system described in the statement.
Examples
0)
{"XXX.XXXX.....X",
 "..X....XXX...X",
 "XXX......X...."}
Returns: 3

We see three tunnels in frame. Note that this fragment could either be right below the ground level or elsewhere in the deep.

1)
{".......X.....",
 ".............",
 "XXX.XXXXXXXXX"}
Returns: 3

A fuller picture of the system could be the following: X.......X.....X X.............X XXXX.XXXXXXXXXX

2)
{".............",
 "XXXXXXXXXXXXX",
 ".............",
 "XXX.......XXX",
 "..........X..",
 "..........XXX"}
Returns: 2

The given fragment could correspond to a system with only two tunnels. A possible picture is: 2.1.............. 2.111111111111111 2...............1 222222.......1111 .............1... .............111. Another possible picture is: ..............1.2 111111111111111.2 1...............2 1111.......222222 ...........2..... ...........222...

3)
{"XXXX...X..",
 "....XXXX.X",
 "XX.......X",
 "..........",
 "....XXXXXX"}
Returns: 4

A possible corresponding picture is: ....1...2..3.4 11111...2..3.4 1....2222.33.4 111.......3..4 .............4 .....444444444

4)
{"X........X..",
 ".........XXX",
 "............",
 "XXXXXXXXXXXX",
 "............",
 "XXXXXXXXXXXX",
 "............",
 ".........XXX",
 "..XXXXXXXX.."}
Returns: 2

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Tunnels with a public method int minimumTunnels(vector<string> frame) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous