# Ema’s Supercomputer challenge

**Problem statement**

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 valid pluses that can be drawn on cells in the grid, and print maximum the product of their areas.

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

**Input Format**

The first line contains two space-separated integers, and . The subsequent lines

contains characters, where each character is either G () or B (). 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 print maximum the product of their areas as an integer.

**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 1 (left) and Sample 2 (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 , so we print .

**Sample 1**

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

is , so we print .

**Solution**

import sys def removePlus(grid, r, c, h, v): l = len(h) # Restore Horizontal index = 0 for i in range(c-l//2, c+l//2+1): grid[r][i] = h[index] index += 1 # Restore Vertical index = 0 for i in range(r-l//2, r+l//2+1): grid[i][c] = v[index] index += 1 def addPlus(grid, r, c, l): # Horizontal h = [] for i in range(c-l//2, c+l//2+1): h.append(grid[r][i]) grid[r][i] = 'X' # Vertical v = [] for i in range(r-l//2, r+l//2+1): if i != r: v.append(grid[i][c]) else: v.append(h[l//2]) grid[i][c] = 'X' return (h,v) def isValidLocation(grid, r, c, l, n, m): if l%2 == 0: return False if c-l//2 < 0: return False if c+l//2 >= m: return False if r-l//2 < 0: return False if r+l//2 >= n: return False # Check Horizontal for i in range(c-l//2, c+l//2+1): if grid[r][i] == 'X' or grid[r][i] == 'B': return False # Check Vertical for i in range(r-l//2, r+l//2+1): if grid[i][c] == 'X' or grid[i][c] == 'B': return False return True def solve(grid, n, m, count, area1, area2): global maximum if count == 2: maximum = max(maximum,area1*area2) else: for r in range(0, n): for c in range(0,m): for l in range(1, min(n,m)+1): if isValidLocation(grid, r, c, l, n, m): # Add one at r,c h,v = addPlus(grid,r,c,l) if count == 0: area1 = (2*l-1) else: area2 = (2*l-1) solve(grid, n, m, count+1, area1, area2) removePlus(grid, r, c, h, v) def main(): f = open("in.txt") n, m = (int(i) for i in f.readline().split()) grid = [] for r in range(0, n): grid.append(list(f.readline().strip())) solve(grid,n,m, 0, 0, 0) print(maximum) maximum = 0 main()

**Notebook file**

https://github.com/lucaslouca/coding-problems/tree/master/python/EmasSupercomputer