Diamonds

TCCC06 Sponsor 3 · 2006-08-22 · by Yarin

TCCC06 Sponsor 3 · 2006-08-22 · by Yarin · Brute Force

Show categories

Class Name: Diamonds

Return Type: int

Method Name: maxRadiusSum

Arg Types: (vector<string>)

Problem Statement

Given a rectangular grid consisting of the characters '#' and '.', find two non-overlapping diamond shapes among the '#' characters such that the sum of their radii is maximized. There is a diamond with radius r centered at x_C, y_C if all characters at position x, y (where |x - x_C| + |y - y_C| + 1 <= r) in the grid are '#'. The left grid below contains a diamond with radius 3. All the '#' characters in the grid are part of this diamond. The right grid contains a diamond with radius 2. It is centered at (2, 1) and contains five '#' characters (coordinates are zero-based).

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

Create a class Diamonds that contains the method maxRadiusSum that takes a String[] grid and returns an int, the maximum sum of the radii of two non-overlapping diamonds.

Notes

A diamond can have radius 0. See example 4.

Constraints

grid will contain between 1 and 50 elements, inclusive.
Each element in grid will contain between 1 and 50 characters, inclusive.
All elements in grid will contain the same number of characters.
Each character in the elements in grid will be either a '#' or a '.'.

Examples

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

Here we have one diamond with radius 3. We can either pick that diamond and an empty diamond, or a diamond with radius 2 (there are 5 of them) and another with radius 1 (a single '#'). In both cases, we end up with a sum of 3. Note that all radius 2 diamonds overlap with each other.

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

This is the grid from the previous example with one extra '#'. We should now choose the diamond with radius 3 and use the extra '#' as our second diamond (radius 1).

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

The largest diamond has radius 4, but we should instead take two diamonds of radius 3 to get the maximum sum.

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

{"##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################","##################################################"}
Returns: 34

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

Coding Area

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