Arcs

SRM 212 · 2004-09-25 · by legakis

SRM 212 · 2004-09-25 · by legakis · Geometry, Search, Simple Math

Show categories

Class Name: Arcs

Return Type: int

Method Name: numArcs

Arg Types: (vector<string>)

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Given a regular grid of size W x H with various squares blocked out, find a path from point (0,0) to point (W,H) that does not pass through any of the blocked-out squares. The path must consist only of 90-degree arcs (quarters of circles). The radius of each arc must be an integer, and therefore begin and end on an integer grid point. The tangents at each end of every arc must be parallel to the x or y axis.

Arcs may intersect the corner of a blocked-out square and even pass between two that share a corner (as shown in the examples below), but may not pass through the interior of any blocked-out square.

The grid will be given as a String[], with a '.' representing an empty square and a '#' representing a blocked-out square. For example, given the following 12 x 8 grid:


  { "....########",
    "###..###...#",
    "..##..#.##.#",
    "...##..#...#",
    "....#..#...#",
    "....#..###..",
    "....####.##.",
    "..........#." }

there is a path from (0,0) to (12,8) consisting of 4 arcs, as shown in the following figure:

Find the path that contains the fewest number of arcs, and return the number of arcs in that path. If there is no path, return -1.

Constraints

grid will contain between 1 and 50 elements, inclusive.
Each element of grid will have a length between 1 and 50, inclusive, and will contain only the characters '.' and '#'.
All elements of grid will have the same length.

Examples

{ "..",
  ".." }
Returns: 1

A single arc of radius 2, centered at (0,2) or (2,0), forms a path from (0,0) to (2,2).

{ "...",
  "..." }
Returns: -1

There can only be a path between opposite corners if the dimensions of the grid are both even or both odd. In this case, the dimensions are 3 x 2, so no path exists.

{ "....",
  ".##.",
  ".##.",
  ".##.",
  ".##.",
  "...." }
Returns: 7

Seven arcs of radius 1 are required in this example.

{ "." }
Returns: 1

{ "....########",
    "###..###...#",
    "..##..#.##.#",
    "...##..#...#",
    "....#..#...#",
    "....#..###..",
    "....####.##.",
    "..........#." }
Returns: 4

This is the example in the problem statement.

{ ".....#................",
  "....#.................",
  "....#.................",
  "....#.....#...........",
  "....#.................",
  "....#....#.#..........",
  "....#.......#####.....",
  "....#.....#.....#.....",
  "....#.....#.....#.....",
  "....#....#.#....#.....",
  "....#....#.#.....#....",
  "....#....#.#......#...",
  "....#....#.#.##.#..###",
  "....#....#....#......." }
Returns: 5

There is a path consisting of 5 arcs, as shown in the following figure. Notice that the path may cross itself:

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

Coding Area

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