# Ema’s Supercomputer – HackerRank Solution

In this post, we will solve Ema’s Supercomputer HackerRank Solution. This problem (Ema’s Supercomputer) is a part of HackerRank Problem Solving series.

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

Given a grid of sizeÂ n x m, each cell in the grid is eitherÂ goodÂ orÂ bad.

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Â goodÂ 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Â 5Â andÂ 9. The product of their areas isÂ 5 x 9 = 45.

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,Â nÂ andÂ m.
Each of the nextÂ nÂ lines contains a string ofÂ mÂ characters where each character is eitherÂ GÂ (good) orÂ BÂ (bad). These strings represent the rows of the grid. If theÂ ythÂ character in theÂ xthÂ line isÂ G, thenÂ (x, y)Â is aÂ goodÂ cell. Otherwise it’s aÂ badÂ cell.

• 2 <= n <= 15
• 2 <= m <= 15

## Output Format

FindÂ 2Â pluses that can be drawn onÂ goodÂ 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 1

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

Explanation Key:

• Green:Â goodÂ cell
• Red:Â badÂ cell
• Blue: possibleÂ pluses.

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

Sample 0
There is enough good space to color oneÂ P3Â plus and oneÂ P1Â plus.Â Area(P3) = 5 units, andÂ Area(P1) = 1 unit. The product of their areas isÂ 5 x 1 = 5.

Sample 1
There is enough good space to color twoÂ P3Â pluses.Â Area(P3) = 5 units. The product of the areas of our twoÂ P3Â pluses isÂ 5 x 5 = 25.

## Solution – Ema’s Supercomputer – HackerRank Solution

### C++

```#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>

struct Plus {
int center_row, center_col, stretch, area;
};

int main() {
int n,m;
std::cin >> n >> m;

std::vector< std::vector<bool> > grid(n, std::vector<bool>(m));

char tmp;
for (auto& row : grid) {
for (auto el : row) {
std::cin >> tmp;
el = tmp == 'G';
}
}

std::vector<Plus> valid_areas;
std::vector<int> arr;
int i,j,up,down,right,left, tmp_i,tmp_j, max_stretch;
for (i = 1; i < n-1; i++) {
for (j = 1; j < m-1; j++) {
if (!grid[i][j]) continue;

up = down = right = left = 0;

tmp_i = i-1;
while(tmp_i >= 0 && grid[tmp_i--][j])
up++;

tmp_i = i+1;
while(tmp_i < n && grid[tmp_i++][j])
down++;

tmp_j = j+1;
while(tmp_j < m && grid[i][tmp_j++])
right++;

tmp_j = j-1;
while(tmp_j >= 0 && grid[i][tmp_j--])
left++;

arr = {up,down,left,right};

for (max_stretch = *std::min_element(arr.begin(),arr.end()); max_stretch >= 0; max_stretch--) {
valid_areas.push_back({
i,j,max_stretch,max_stretch*4+1
});
}
}
}
auto comp = [](Plus l, Plus r){return l.area > r.area;};
std::sort(valid_areas.begin(),valid_areas.end(), comp);

Plus a,b;

int s = valid_areas.size();
std::vector<int> results;
for (i = 0; i < s; i++) {

a = valid_areas[i];

for (j = i+1; j < s; j++) {

b = valid_areas[j];

bool row, arow, col, acol;
row = b.center_row < a.center_row;
arow = b.center_row > a.center_row;

col = b.center_col < a.center_col;
acol = b.center_col > a.center_col;

if (row) {
if (col) {
if ((b.stretch + b.center_row >= a.center_row && a.center_col - a.stretch <= b.center_col)
|| (b.center_col + b.stretch >= a.center_col && a.center_row - a.stretch <= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else if (acol) {
if ((b.stretch + b.center_row >= a.center_row && a.center_col + a.stretch >= b.center_col)
|| (b.center_col - b.stretch <= a.center_col && a.center_row - a.stretch <= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else {
if (b.stretch + b.center_col >= a.center_col - a.stretch) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
}
} else if (arow) {
if (col) {
if ((b.center_row - b.stretch <= a.center_row && a.center_col - a.stretch <= b.center_col)
|| (b.center_col + b.stretch >= a.center_col && a.center_row + a.stretch >= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else if (acol) {
if ((b.center_row - b.stretch <= a.center_row && a.center_col + a.stretch >= b.center_col)
|| (b.center_col - b.stretch <= a.center_col && a.center_row + a.stretch >= b.center_row)) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
} else {
if (b.center_col - b.stretch <= a.center_col + a.stretch) {
continue;
} else {
results.push_back(a.area * b.area);
break;
}
}
} else {
if (col) {
if (b.stretch + b.center_col < a.center_col - a.stretch) {
results.push_back(a.area * b.area);
break;
}
} else if (acol) {
if (b.center_col - b.stretch > a.center_col + a.stretch) {
results.push_back(a.area * b.area);
break;
}
} // else continue
}
}
}

std::cout << *std::max_element(results.begin(),results.end()) << std::endl;

return 0;
}
```

### Python

```def get_pluses(x, y, grid, width, height):
pluses = []
if grid[y][x]:
dist = 0

for i in range(0, max(width, height)):
if y-i < 0 or not grid[y-i][x]:
break
if y+i >= height or not grid[y+i][x]:
break
if x-i < 0 or not grid[y][x-i]:
break
if x+i >= width or not grid[y][x+i]:
break
pluses.append((x, y, dist, dist * 4 + 1))
dist += 1

return pluses

def line_intersect(l1, l2):
return l1[0] <= l2[2] and l1[2] >= l2[0] and l1[1] <= l2[3] and l1[3] >= l2[1]

def intersect(p1, p2):
if p1[0] == p2[0] and p1[1] == p2[1]:
return True

l1 = p1[0] - p1[2], p1[1], p1[0] + p1[2], p1[1]
l2 = p1[0], p1[1] - p1[2], p1[0], p1[1] + p1[2]
l3 = p2[0] - p2[2], p2[1], p2[0] + p2[2], p2[1]
l4 = p2[0], p2[1] - p2[2], p2[0], p2[1] + p2[2]

return line_intersect(l1, l3) or line_intersect(l1, l4) or line_intersect(l2, l3) or line_intersect(l2, l4)

if __name__ == '__main__':
n, m = map(int, input().strip().split(' '))

grid = []
for i in range(n):
grid.append([True if x == 'G' else False for x in input().strip()])

pluses = []

for y in range(n):
for x in range(m):
pluses += get_pluses(x, y, grid, m, n)

if len(pluses) <= 1:
print(0)
else:
best = 0
for i in range(len(pluses)-1):
for j in range(i+1, len(pluses)):
if not intersect(pluses[i], pluses[j]):
best = max(best, pluses[i][3] * pluses[j][3])

print(best)
```

### Java

```import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {

static class ValidPlus{

public int area;
public int length;
public ArrayList<Cell> cells = new ArrayList<>();

public ValidPlus() {
area = 1;
length = 1;
}

public ValidPlus(ValidPlus anotherValidPlus) {
this.area = anotherValidPlus.area;
this.length = anotherValidPlus.length;
this.cells = new ArrayList<Cell>(anotherValidPlus.cells);
}

public void addCell(Cell cell) {
}

}

static class Cell {

public int row;
public int column;

public Cell(int row, int column) {
super();
this.row = row;
this.column = column;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + column;
result = prime * result + row;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Cell other = (Cell) obj;
if (column != other.column)
return false;
if (row != other.row)
return false;
return true;
}

}

public static void main(String[] args) throws CloneNotSupportedException {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int m = sc.nextInt();

ArrayList<ValidPlus> validPluses = new ArrayList<>();

char[][] map = new char[n][m];

for (int i = 0; i < n; i++) {
String line = sc.next();
for (int j = 0; j < m; j++) {
map[i][j] = line.charAt(j);
}
}

sc.close();

// We save all the valid pluses
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char currentCell = map[i][j];
if (currentCell == 'G') {
boolean thereIsGoodCell = true;
// Everytime we find a good cell, we create a valid plus
// with length 1
ValidPlus validPlus = new ValidPlus();
int length = 1;
while (thereIsGoodCell) {
// We check if it's possible to extend the valid plus in
// all the four directions
if ((i - length >= 0 && map[i - length][j] == 'G')
&& (i + length < n && map[i + length][j] == 'G')
&& (j - length >= 0 && map[i][j - length] == 'G')
&& (j + length < m && map[i][j + length] == 'G')) {
// If it's possible, we create a new valid plus
ValidPlus newValidPlus = new ValidPlus(validPlus);
newValidPlus.addCell(new Cell(i - length, j));
newValidPlus.addCell(new Cell(i + length, j));
newValidPlus.addCell(new Cell(i, j - length));
newValidPlus.addCell(new Cell(i, j + length));
length++;
newValidPlus.area = 1 + (4 * (length - 1));
newValidPlus.length = length;
validPlus = new ValidPlus(newValidPlus);
} else {
thereIsGoodCell = false;
}
}

}
}
}

int maxArea = 0;

// We compare all the valid pluses
for (int i = 0; i < validPluses.size(); i++) {
ValidPlus currentValidPlus = validPluses.get(i);
for (int j = i + 1; j < validPluses.size(); j++) {
ValidPlus otherValidPlus = validPluses.get(j);
int currentArea = currentValidPlus.area * otherValidPlus.area;
if (currentArea > maxArea) {
// If we have found a new max area, we have to check that
// the valid pluses don't overlap.
// To do this, we get the cells occupied by the two valid
// pluses
ArrayList<Cell> currentCells = currentValidPlus.cells;
ArrayList<Cell> otherCells = otherValidPlus.cells;
List<Cell> commonCells = new ArrayList<Cell>(currentCells);
commonCells.retainAll(otherCells);
// If the valid pluses don't have common cells, it's OK
if (commonCells.size() == 0) {
maxArea = currentArea;
}
}

}
}

System.out.println(maxArea);

}

}
```

Note: This problem (Ema’s Supercomputer) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.