Ema's Supercomputer

Ema built a quantum computer! Help her test its capabilities by solving the problem below.

---

Given a grid of size , each cell in the grid is either  or .

A valid plus is defined here as the crossing of two segments (horizontal and vertical) of equal lengths. These lengths must be odd, and the middle cell of its horizontal segment must cross the middle cell of its vertical segment.

In the diagram below, the blue pluses are valid and the orange ones are not valid. 

Find the two largest valid pluses that can be drawn on  cells in the grid, and return an integer denoting the maximum product of their areas. In the above diagrams, our largest pluses have areas of  and . The product of their areas is .

Note: The two pluses cannot overlap, and the product of their areas should be maximal.

Function Description

Complete the twoPluses function in the editor below. It should return an integer that represents the area of the two largest pluses.

twoPluses has the following parameter(s):

• grid: an array of strings where each string represents a row and each character of the string represents a column of that row

Input Format

The first line contains two space-separated integers,  and .
Each of the next  lines contains a string of  characters where each character is either G () or B (). These strings represent the rows of the grid. If the  character in the  line is G, then  is a  cell. Otherwise it's a  cell.

Constraints

• 
  
• 
  

Output Format

Find  pluses that can be drawn on  cells of the grid, and return an integer denoting the maximum product of their areas.

Sample Input 0

5 6
GGGGGG
GBBBGB
GGGGGG
GGBBGB
GGGGGG

Sample Output 0

5

Sample Input 1

6 6
BGBBGB
GGGGGG
BGBBGB
GGGGGG
BGBBGB
BGBBGB

Sample Output 1

25

Explanation

Here are two possible solutions for Sample 0 (left) and Sample 1 (right): 

Explanation Key:

• Green:  cell
• Red:  cell
• Blue: possible .

For the explanation below, we will refer to a plus of length  as .

Sample 0
There is enough good space to color one  plus and one  plus. , and . The product of their areas is .

Sample 1
There is enough good space to color two  pluses. . The product of the areas of our two  pluses is .

php

<?php

// Complete the twoPluses function below.

function twoPluses($grid) {

$arr = array();

$ar = array();

foreach($grid as $g) {

$arr[] = str_split($g);

}

$cnts = array();

//$lgoodcnt = 0;

for($i =0; $i< count($arr); $i++) {

for($j =0; $j< count($arr[$i]); $j++) {

if($arr[$i][$j] == 'G') {

//$lgoodcnt++;

$cnt = 0;

$as = array();

$as[] = $i.'-'.$j;

while( !empty($arr[$i-$cnt][$j]) && $arr[$i-$cnt][$j] == 'G'

&& !empty($arr[$i+$cnt][$j]) && $arr[$i+$cnt][$j] == 'G'

&& !empty($arr[$i][$j -$cnt]) && $arr[$i][$j-$cnt] == 'G'

&& !empty($arr[$i][$j+$cnt]) && $arr[$i][$j+$cnt] == 'G') {

$as = array_merge(

$as,

array(

($i-$cnt).'-'.$j,

($i+$cnt).'-'.$j,

$i.'-'.($j-$cnt),

$i.'-'.($j+$cnt)

)

);

$ar[] = array('cnt' => $cnt, 'as' => $as);

$cnts[] = $cnt;

$cnt++;

}

//$cnt--;

}

}

}

$max = 0;

if(count($ar) < 2) {

return 0;

}

for($i = 0; $i < count($ar)-1; $i++) {

for($j = $i+1; $j < count($ar); $j++) {

$c1 = $ar[$i]['cnt'];

$as1 = $ar[$i]['as'];

$c2 = $ar[$j]['cnt'];

$as2 = $ar[$j]['as'];

if( count(array_intersect($as1,$as2)) == 0 )

{

$max1 = ($c1*4+1)*($c2*4+1);

if($max1 > $max) {

$max = $max1;

}

}

}

}

return $max;

}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$stdin = fopen("php://stdin", "r");

fscanf($stdin, "%[^\n]", $nm_temp);

$nm = explode(' ', $nm_temp);

$n = intval($nm[0]);

$m = intval($nm[1]);

$grid = array();

for ($i = 0; $i < $n; $i++) {

$grid_item = '';

fscanf($stdin, "%[^\n]", $grid_item);

$grid[] = $grid_item;

}

$result = twoPluses($grid);

fwrite($fptr, $result . "\n");

fclose($stdin);

fclose($fptr);