# Hackerrank Ema's Supercomputer Solution

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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 .

### Solution in java8

Approach 1.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

// Complete the twoPluses function below.
static int twoPluses(String[] grid) {
int len1=grid.length;
int len2=grid[0].length();
int k=0;
int u=0;
char arr[][]=new char[len1][len2];
int max1=1;
int max2=Integer.MIN_VALUE;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
arr[i][j]=grid[i].charAt(j);
}
}
for(int i=1;i<len1-1;i++)
{
//int len2=grid[i].length;
for(int j=1;j<len2-1;j++)
{
int m=1;
int res=0;
while( i-m >=0 && i+m<len1 && j-m >=0 && j+m < len2 && arr[i-m][j]=='G' && arr[i][j-m]=='G'&& arr[i][j+m]=='G' && arr[i+m][j]=='G')
{
arr[i][j]='V';
arr[i-m][j]='V';
arr[i+m][j]='V';
arr[i][j-m]='V';
arr[i][j+m]='V';

res=res+4;
m=m+1;
}
res=res+1;
//System.out.println("."+)
System.out.println("i: "+i+"j: "+j+"res: "+res);
// int x =Math.max(Math.max(max1,max2),res);

k=Math.max(Math.max(max1,max2),res);
if(k==max1)
{
u=Math.max(max2,res);
}
if(k==max2)
{
u=Math.max(max1,res);
}
if(k==res)
{
u=Math.max(max2,max1);
}
max1=k;
max2=u;
}

}
System.out.println("k "+k+"u "+u);
return max1*max2;

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nm = scanner.nextLine().split(" ");

int n = Integer.parseInt(nm[0]);

int m = Integer.parseInt(nm[1]);

String[] grid = new String[n];

for (int i = 0; i < n; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}

int result = twoPluses(grid);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}


Approach 2.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

// Complete the twoPluses function below.
static int twoPluses(String[] grid) {
char a[][]=new char[grid.length][grid[0].length()];
for(int i=0;i<grid.length;i++){
a[i] = grid[i].toCharArray();
}
int min = 1,max = 1,count=1,x=0;
for(int i=1;i<grid.length-1;i++){
for(int j=1;j<grid[0].length()-1;j++){
if(a[i][j]=='G' && a[i-1][j]=='G' && a[i+1][j]=='G' && a[i][j-1]=='G' && a[i][j+1]=='G'){
int left = j-1;
int top = i-1;
int right = j+1;
int bottom = i+1;
while(top>=0 && bottom<a.length && left>=0 && right <a[0].length && a[top][j]=='G' && a[bottom][j]=='G' && a[i][left]=='G' && a[i][right]=='G')
{
a[top][j]='0';
a[bottom][j]='0';
a[i][left]='0';
a[i][right]='0';
count+=4;
top--;
bottom++;
left--;
right++;
}
if(count>max){
min=max;
max=count;
}else if(count>min){
min=count;
}
count=1;
}
}
}
return min*max;
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nm = scanner.nextLine().split(" ");

int n = Integer.parseInt(nm[0]);

int m = Integer.parseInt(nm[1]);

String[] grid = new String[n];

for (int i = 0; i < n; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}

int result = twoPluses(grid);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}


Approach 3.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

// Complete the twoPluses function below.
static int twoPluses(String[] grid) {
int n=grid.length;
int m=grid[0].length();
int cnt=0;
int area=1;
int cntG=0;
for(int i=0;i<n;i++)
{
char ch[]=grid[i].toCharArray();
for(int j=0;j<m;j++)
{
if(ch[j]=='G')
{
cntG++;
int min=Math.min(n-i-1,m-j-1);
int k=j+1;
int l=j-1;
int length=0;

while(k<m && k<=min+j && l>=0 && l>=j-min)
{
if(ch[k]=='G' && ch[l]=='G')
{
length++;
}
else
break;
k++;
l--;
}

k=i+1;
l=i-1;
int height=0;
while(k<n && k<=min+i && l>=0 && l>=i-min)
{
if(grid[k].charAt(j)=='G' && grid[l].charAt(j)=='G')
{
height++;
}
else
break;
k++;
l--;
}

if(length==height && cnt<2 && length!=0)
{
cnt++;
area*=2*(length+height)+1;
}

System.out.println("i "+i+" j "+j+" length "+length+" height "+height+" cnt "+cnt+" area "+area);
}
}
}
if(cnt==1)
area*=1;

return area;

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

String[] nm = scanner.nextLine().split(" ");

int n = Integer.parseInt(nm[0]);

int m = Integer.parseInt(nm[1]);

String[] grid = new String[n];

for (int i = 0; i < n; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}

int result = twoPluses(grid);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}


### Solution in python3

Approach 1.

Approach 2.

Approach 3.

def twoPluses(ri, c, grid):
tem = []
tem.append(["O"] * (ri + 2))
for x in grid:
tem.append(["O"] + list(x) + ["O"])
tem.append(["O"] * (ri + 2))
grid = tem
# print(grid)
ans=0
for e in range(1, ri + 1):
for v in range(1, c + 1):
r = 0
# check adjacent 4 cells of [e][v] when r >0
while grid[e + r][v] == "G" and grid[e - r][v] == "G" and grid[e][v + r] == "G" and grid[e][v - r] == "G":
grid[e + r][v] =grid[e - r][v] =grid[e][v + r] =grid[e][v - r] = "g"#to avoid overlapping of 2 pluses at that instance
for E in range(1, ri + 1):#2nd plus
for V in range(1, c + 1):
R = 0
# check adjacent 4 cells of [e][v] when r >0
while grid[E + R][V] == "G" and grid[E - R][V] == "G" and grid[E][V + R] == "G" and grid[E][
V - R] == "G":
ans=max(ans,(4*r +1)*(4*R +1))
R+=1
r+=1
#revert back to "G" for each "g"
r=0
while grid[e + r][v] == "g" and grid[e - r][v] == "g" and grid[e][v + r] == "g" and grid[e][v - r] == "g":
grid[e + r][v] = grid[e - r][v] = grid[e][v + r] = grid[e][v - r] = "G"
r+=1

return ans

if __name__ == '__main__':

nm = input().split()

n = int(nm[0])

m = int(nm[1])

grid = []

for _ in range(n):
grid_item = input()
grid.append(grid_item)

result = twoPluses(n, m, grid)

print(result)


### Solution in cpp

Approach 1.


#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
int area(int l) { return 4*l+1; }
int value(int y, int x, int l1, int l2) {
if (y > x) swap(y, x);
int ans = 0;
if (y == 0) {
repeat (t,x) {
ans = max(ans, area(min(t,l1)) * area(min(x-t-1,l2)));
}
} else {
repeat (t,l1+1) {
int u =
t < y ? l2 :
t < x ? min(x-1, l2) :
min(y-1, l2);
ans = max(ans, area(t) * area(u));
}
}
return ans;
}
int main() {
int h, w; cin >> h >> w;
vector<vector<bool> > is_good(h, vector<bool>(w));
repeat (y,h) repeat (x,w) {
char c; cin >> c;
is_good[y][x] = c == 'G';
}
auto is_on_field = [=](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
vector<vector<int> > l(h, vector<int>(w)); // possible length of 4 bars
repeat (y,h) repeat (x,w) {
while (true) {
bool valid = true;
repeat (i,4) {
int ny = y + l[y][x] * dy[i];
int nx = x + l[y][x] * dx[i];
if (not is_on_field(ny, nx) or not is_good[ny][nx]) {
valid = false;
break;
}
}
if (not valid) break;
++ l[y][x];
}
}
int ans = 0;
repeat (y1,h) repeat (x1,w) if (l[y1][x1]) {
repeat (y2,h) repeat (x2,w) if (l[y2][x2]) {
if (y1 != y2 or x1 != x2) {
ans = max(ans, value(abs(y1-y2), abs(x1-x2), l[y1][x1]-1, l[y2][x2]-1));
}
}
}
cout << ans << endl;
return 0;
}


Approach 2.

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<string> G;

bool nextLevelValid(int x, int y, int l) {
if (x + l >= n || x - l < 0 || y + l >= m || y - l < 0) {
return false;
}
if (G[x + l][y] == 'B' || G[x - l][y] == 'B' || G[x][y + l] == 'B' ||
G[x][y - l] == 'B') {
return false;
}
return true;
}

bool compare(vector<int> a, vector<int> b) { return a[2] > b[2]; }

bool validCrosses(vector<int> a, vector<int> b) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
G[i][j] = 'G';
}
}
for (int i = 0; i < a[2]; ++i) {
G[a[0] + i][a[1]] = 'B';
G[a[0] - i][a[1]] = 'B';
G[a[0]][a[1] + i] = 'B';
G[a[0]][a[1] - i] = 'B';
}
for (int i = 0; i < b[2]; ++i) {
if (G[b[0] + i][b[1]] == 'B' || G[b[0] - i][b[1]] == 'B' ||
G[b[0]][b[1] + i] == 'B' || G[b[0]][b[1] - i] == 'B') {
return false;
}
}
return true;
}

int main() {
cin >> n >> m;
G = vector<string>(n);
vector<vector<int>> A(n, vector<int>(m, 0));
vector<vector<int>> C;
for (int i = 0; i < n; ++i) {
cin >> G[i];
}
// cout << "\n\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (G[i][j] == 'G') {
int level = 1;
while (nextLevelValid(i, j, level)) {
++level;
}
A[i][j] = level;
// cout << level << " ";
C.push_back({i, j, level});
} else {
// cout << "0 ";
}
}
// cout << "\n";
}
// cout << "\n\n";
sort(C.begin(), C.end(), compare);
int max = 0;
for (int i = 0; i < C.size() - 1; ++i) {
for (int j = i + 1; j < C.size(); ++j) {
for (int l1 = 1; l1 <= C[i][2]; ++l1) {
for (int l2 = 1; l2 <= C[j][2]; ++l2) {
vector<int> C1 = C[i], C2 = C[j];
C1[2] = l1, C2[2] = l2;
if (validCrosses(C1, C2)) {
int loc = (C1[2] * 4 - 3) * (C2[2] * 4 - 3);
if (loc > max) {
max = loc;
}
}
}
}
}
}
cout << max << "\n";
return 0;
}

Approach 3.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the twoPluses function below.
int onePluse(vector<string> grid)
{
int m = 0;
for(int i=0;i<grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == 'B') continue;
int k = 0;
while(i-k>=0 && j-k >=0 && i+k < grid.size() && j +k < grid[0].size() && grid[i-k][j] == 'G' && grid[i+k][j] == 'G' && grid[i][j-k] == 'G' && grid[i][j+k] == 'G')
{
k++;
}
if(4*k-3 > m) m = 4*k-3;
}
}
return m;
}
int twoPluses(vector<string> grid) {
int m = 0;
for(int i=0;i<grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == 'B') continue;
vector<string> grid2(grid);
int k = 0;
while(i-k>=0 && j-k >=0 && i+k < grid.size() && j +k < grid[0].size() &&
grid[i-k][j] == 'G' && grid[i+k][j] == 'G' && grid[i][j-k] == 'G' && grid[i][j+k] == 'G')
{
grid2[i-k][j] = 'B';
grid2[i+k][j] = 'B';
grid2[i][j-k] = 'B';
grid2[i][j+k] = 'B';
k++;
int temp = 4*k-3;
int temp2 = onePluse(grid2);
if(temp * temp2 > m) m = temp *temp2;
}
}
}
return m;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

string nm_temp;
getline(cin, nm_temp);

vector<string> nm = split_string(nm_temp);

int n = stoi(nm[0]);

int m = stoi(nm[1]);

vector<string> grid(n);

for (int i = 0; i < n; i++) {
string grid_item;
getline(cin, grid_item);

grid[i] = grid_item;
}

int result = twoPluses(grid);

fout << result << "\n";

fout.close();

return 0;
}

vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});

input_string.erase(new_end, input_string.end());

while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}

vector<string> splits;
char delimiter = ' ';

size_t i = 0;
size_t pos = input_string.find(delimiter);

while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));

i = pos + 1;
pos = input_string.find(delimiter, i);
}

splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

return splits;
}