Connection Status:
Competition Arena > LoopyPath

LoopyPath

TCO 2014 Finals · 2014-03-26 · by lg5293

TCO 2014 Finals · 2014-03-26 · by lg5293 · Graph Theory
Class Name: LoopyPath
Return Type: int
Method Name: findMinimumCycle
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You have a rectangle that is divided into a grid of unit squares. The corners and sides of those squares will be called grid points and grid lines, respectively. Each square contains either a 0 or a 1. You are given these numbers in a String[] grid. The elements of grid represent the rows of squares from top to bottom. In each element, the characters represent the squares in that row from left to right. Each of those characters is either '0' or '1'.

You want to take a walk along some grid lines. The walk must satisfy the following properties:

  1. You must both start and end the walk in the top left grid point.
  2. In each step, you have to walk along a single grid line (i.e., move by 1 up, down, left, or right).
  3. Your walk must visit each grid point at least once.
  4. Your walk must satisfy the additional property described in the next paragraph.

Consider any walk that satisfies the first three properties. Imagine that a boy is standing in the middle of a given square and a girl takes the entire walk once (both starting and ending in the top left grid point). While the girl walks, the boy stays in place but rotates so that he always faces the girl's current position. Clearly, when the girl ends the walk, the net result for the boy will be some number of full turns. For each square in the grid, the number written in the square must correspond to the net number of clockwise turns the boy would make if he stood in that square. (In other words, if the square contains a 0, the boy standing in that square must rotate by the same total amount clockwise and counterclockwise, and if the square contains a 1, the boy's total clockwise rotation must be 360 degrees more than the boy's total counterclockwise rotation.)

You are given the String[] grid. Return the smallest L such that in the given grid there is a valid walk with L steps, or -1 if no valid walk exists.

Notes

  • The walk may visit each grid point, including the top left grid point, arbitrarily many times.

Constraints

  • grid will contain between 1 and 50 elements, inclusive.
  • Each element of grid will contain between 1 and 50 characters, inclusive.
  • Each element of grid will contain the same number of characters.
  • Each character in each element of grid will be either '0' or '1'.
Examples
0)
{"111"}
Returns: 8

The optimal walk is to go around the boundary of the grid clockwise. This gives us a path of length 8.

1)
{"10",
 "11"}
Returns: 10

We need to visit every grid point. Here is one example of an optimal walk. This walk has length 10.

2)
{"111",
 "111",
 "111"}
Returns: 20
3)
{"1110000",
 "0000111"}
Returns: 34
4)
{
"1110001110001111111000111",
"1110001110001111111000111",
"1110001110000011100000111",
"1111111110000011100000111",
"1111111110000011100000111",
"1110001110000011100000000",
"1110001110001111111000111",
"1110001110001111111000111"
}
Returns: 364

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

Coding Area

Language: C++17 · define a public class LoopyPath with a public method int findMinimumCycle(vector<string> grid) · 103 test cases · 2 s / 256 MB per case

Submitting as anonymous