Diamonds | Topcoder Archive

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.

Definition

Class:: Diamonds
Method:: maxRadiusSum
Parameters:: String[]
Returns:: int
Method signature:: int maxRadiusSum(String[] grid)
(be sure your method is public)

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: 1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.