Ema’s Supercomputer HackerRank Solution in C, C++, Java, Python

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

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

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. pluseses.png

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*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 line is G, then (x,y) is a goo cell. Otherwise it’s a bad cell.

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`

Ema’s Supercomputer HackerRank Solution in C

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

char grid[15][16], grid2[15][16];
int n, m;

void copygrid() {
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) grid2[i][j] = grid[i][j];
}

int main() {
int area[] = {0, 1, 5, 9, 13, 17, 21, 25, 29, 33};
int i, j, step, max = 0, temp;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%s", grid[i]);
}
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (grid[i][j] == 'G') {
copygrid();
step = 1;
grid2[i][j] = 'B';
while (1) {
if (i - step < 0 || i + step > n - 1 || j - step < 0 || j + step > m - 1) break;
if (grid2[i-step][j] == 'B' || grid2[i+step][j] == 'B' || grid2[i][j-step] == 'B' || grid2[i][j+step] == 'B') break;
grid2[i-step][j] = 'B';
grid2[i+step][j] = 'B';
grid2[i][j-step] = 'B';
grid2[i][j+step] = 'B';
step++;
}
temp = area[step];
int k, l;
for (k = 0; k < n; k++) {
for (l = 0; l < m; l++) {
if (grid2[k][l] == 'G') {
step = 1;
while (1) {
if (k - step < 0 || k + step > n - 1 || l - step < 0 || l + step > m - 1) break;
if (grid2[k-step][l] == 'B' || grid2[k+step][l] == 'B' || grid2[k][l-step] == 'B' || grid2[k][l+step] == 'B') break;
step++;
}
if (temp * area[step] > max) max = temp * area[step];
}
}
}
}
}
}
printf("%d", max);
return 0;
}```

Ema’s Supercomputer HackerRank Solution in C++

```#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

int main() {
int N; int M;
while(~scanf("%d%d", &N, &M)) {
vector<string> a(N);
rep(i, N) cin >> a[i];
int ans = 0;
rep(y0, N) rep(x0, M) rer(s0, 1, min({ y0 + 1, N - y0, x0 + 1, M - x0 })) {
vector<vector<bool> > good(N, vector<bool>(M));
rep(i, N) rep(j, M)
good[i][j] = a[i][j] == 'G';
bool ok = true;
rer(d, -s0 + 1, s0 - 1) {
ok &= good[y0 + d][x0];
ok &= good[y0][x0 + d];
good[y0 + d][x0] = good[y0][x0 + d] = false;
}
if(!ok) continue;
rep(y1, N) rep(x1, M) {
int maxs1 = min({ y1 + 1, N - y1, x1 + 1, M - x1 });
int s1 = maxs1;
rer(d, -maxs1 + 1, maxs1 - 1) {
if(!good[y1 + d][x1] || !good[y1][x1 + d])
amin(s1, abs(d) - 1);
}
if(s1 > 0)
amax(ans, ((s0 - 1) * 4 + 1) * ((s1 - 1) * 4 + 1));
}
}
printf("%d\n", ans);
}
return 0;
}```

Ema’s Supercomputer HackerRank Solution in Java

```import java.io.*;
import java.util.*;

public class Solution {
private StringTokenizer line;
private PrintWriter out;

public void solve() throws IOException {
int n = nextInt();
int m = nextInt();
char[][] a = new char[n][];
for (int i = 0; i < n; i++) {
a[i] = nextToken().toCharArray();
}
int res = 0;
int[][] colors = new int[n][m];
int color = 13;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
color++;
for (int len = 0; ; len++) {
if (i + len >= n || i - len < 0 || j + len >= m || j - len < 0 ||
a[i + len][j] != 'G' || a[i - len][j] != 'G' || a[i][j + len] != 'G' || a[i][j - len] != 'G') {
break;
}
colors[i + len][j] = color;
colors[i - len][j] = color;
colors[i][j + len] = color;
colors[i][j - len] = color;
for (int x = i; x < n; x++) {
for (int y = 0; y < m; y++) {
for (int l = 0; ; l++) {
if (x + l >= n || x - l < 0 || y + l >= m || y - l < 0 ||
a[x + l][y] != 'G' || a[x - l][y] != 'G' || a[x][y + l] != 'G' || a[x][y - l] != 'G') {
break;
}
if (colors[x + l][y] == color || colors[x - l][y] == color ||
colors[x][y + l] == color || colors[x][y - l] == color) {
break;
}
res = Math.max(res, (len*4+1)*(l * 4 + 1));
}
}
}
}
}
}
out.println(res);
}

public static void main(String[] args) throws IOException {
new Solution().run(args);
}

public void run(String[] args) throws IOException {
if (args.length > 0 && "DEBUG_MODE".equals(args[0])) {
} else {
}
out = new PrintWriter(System.out);
//        out = new PrintWriter("output.txt");

//        int t = nextInt();
int t = 1;
for (int i = 0; i < t; i++) {
//            out.print("Case #" + (i + 1) + ": ");
solve();
}

in.close();
out.flush();
out.close();
}

private int[] nextIntArray(int n) throws IOException {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}

private long[] nextLongArray(int n) throws IOException {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}

private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}

private long nextLong() throws IOException {
return Long.parseLong(nextToken());
}

private double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}

private String nextToken() throws IOException {
while (line == null || !line.hasMoreTokens()) {
}
return line.nextToken();
}

private static class Pii {
private int key;
private int value;

public Pii(int key, int value) {
this.key = key;
this.value = value;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Pii pii = (Pii) o;

if (key != pii.key) return false;
return value == pii.value;

}

@Override
public int hashCode() {
int result = key;
result = 31 * result + value;
return result;
}
}

private static class Pair<K, V> {
private K key;
private V value;

public Pair(K key, V value) {
this.key = key;
this.value = value;
}

public K getKey() {
return key;
}

public V getValue() {
return value;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Pair<?, ?> pair = (Pair<?, ?>) o;

if (key != null ? !key.equals(pair.key) : pair.key != null) return false;
return !(value != null ? !value.equals(pair.value) : pair.value != null);

}

@Override
public int hashCode() {
int result = key != null ? key.hashCode() : 0;
result = 31 * result + (value != null ? value.hashCode() : 0);
return result;
}
}
}```

Ema’s Supercomputer HackerRank Solution in Python

```n, m = map(int, raw_input().split())
X = []
for _ in xrange(n):
X.append(raw_input())
ans = 0
C = [[0 for i in xrange(m)] for j in xrange(n)]
def makeplus(a, b, l):
C[a][b] += 1
for ii in xrange(l):
C[a - 1 - ii][b] += 1
C[a + 1 + ii][b] += 1
C[a][b - 1 - ii] += 1
C[a][b + 1 + ii] += 1
for i in xrange(n):
for j in xrange(m):
if X[i][j] != "B":
for l1 in xrange(min(n - i - 1, m - j - 1, i, j) + 1):
for k in xrange(i, n):
for l in xrange(m):
if X[k][l] != "B":
for l2 in xrange(min(n - k - 1, m - l - 1, k, l) + 1):
makeplus(i, j, l1)
makeplus(k, l, l2)
if not any(any((C[i][j] > 0 and X[i][j] == "B") or (C[i][j] > 1) for j in xrange(m)) for i in xrange(n)):
ans = max((l1 * 4 + 1) * (l2 * 4 + 1), ans)
C = [[0 for ii in xrange(m)] for jj in xrange(n)]
print ans```

Ema’s Supercomputer HackerRank Solution in C#

```using System;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;
using System.Globalization;
using System.Collections.Generic;
using kp.Algo;
using kp.Algo.IO;

namespace CodeForces
{
internal class Solution
{
const int StackSize = 20 * 1024 * 1024;

private void Solve()
{
int rows = NextInt();
int cols = NextInt();
var s = new string[rows];
for (int i = 0; i < rows; i++)
{
s[i] = NextLine().Trim();
}
int res = 0;
var w = new int[rows, cols];
int step = 0;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (s[i][j] == 'G')
{
w[i, j] = ++step;
int ur = i, dr = i, lc = j, rc = j;
var sq = 1;
var len = 0;
while (true)
{
for (int ii = 0; ii < rows; ii++)
{
for (int jj = 0; jj < cols; jj++)
{
if (s[ii][jj] == 'G' && (ii != i || jj != j))
{
int ur2 = ii, dr2 = ii, lc2 = jj, rc2 = jj;
var sq2 = 1;
while (true)
{
res = Math.Max(res, sq * sq2);

if (--ur2 < 0 || s[ur2][jj] != 'G' || w[ur2, jj] == step) break;
if (++dr2 == rows || s[dr2][jj] != 'G' || w[dr2, jj] == step) break;
if (--lc2 < 0 || s[ii][lc2] != 'G' || w[ii, lc2] == step) break;
if (++rc2 == cols || s[ii][rc2] != 'G' || w[ii, rc2] == step) break;
sq2 += 4;
}
}
}
}

if (--ur < 0 || s[ur][j] != 'G') break;
if (++dr == rows || s[dr][j] != 'G') break;
if (--lc < 0 || s[i][lc] != 'G') break;
if (++rc == cols || s[i][rc] != 'G') break;
sq += 4;
++len;
w[ur, j] = step;
w[dr, j] = step;
w[i, lc] = step;
w[i, rc] = step;
}
}
}
}

Out.WriteLine(res);
}

#region Local wireup

public int[] NextIntArray(int size)
{
var res = new int[size];
for (int i = 0; i < size; ++i) res[i] = NextInt();
return res;
}

public long[] NextLongArray(int size)
{
var res = new long[size];
for (int i = 0; i < size; ++i) res[i] = NextLong();
return res;
}

public double[] NextDoubleArray(int size)
{
var res = new double[size];
for (int i = 0; i < size; ++i) res[i] = NextDouble();
return res;
}

public int NextInt()
{
return _in.NextInt();
}

public long NextLong()
{
return _in.NextLong();
}

public string NextLine()
{
return _in.NextLine();
}

public double NextDouble()
{
return _in.NextDouble();
}

Scanner _in;
static readonly TextWriter Out = Console.Out;

void Start()
{
#if KP_HOME
_in = new Scanner("input.txt");
var timer = new Stopwatch();
timer.Start();
#else
_in = new Scanner( Console.In, false );
#endif
var t = new Thread(Solve, StackSize);
t.Start();
t.Join();
#if KP_HOME
timer.Stop();
Console.WriteLine(string.Format(CultureInfo.InvariantCulture, "Done in {0} seconds.\nPress <Enter> to exit.", timer.ElapsedMilliseconds / 1000.0));
#endif
}

static void Main()
{
new Solution().Start();
}

#endregion
}
}

namespace kp.Algo { }

namespace kp.Algo.IO
{
public class Scanner : IDisposable
{
#region Fields

int _length, _pos;

#endregion

#region .ctors

{
_bufferSize = bufferSize;
_buffer = new char[_bufferSize];
FillBuffer( false );
}

public Scanner( string fileName ) : this( new System.IO.StreamReader( fileName, System.Text.Encoding.Default ), true ) { }

#endregion

#region IDisposable Members

public void Dispose()
{
{
}
}

#endregion

#region Properties

public bool Eof
{
get
{
if ( _pos < _length ) return false;
FillBuffer( false );
return _pos >= _length;
}
}

#endregion

#region Methods

private char NextChar()
{
if ( _pos < _length ) return _buffer[_pos++];
FillBuffer( true );
return _buffer[_pos++];
}

private char PeekNextChar()
{
if ( _pos < _length ) return _buffer[_pos];
FillBuffer( true );
return _buffer[_pos];
}

private void FillBuffer( bool throwOnEof )
{
if ( throwOnEof && Eof )
{
throw new System.IO.IOException( "Can't read beyond the end of file" );
}
_pos = 0;
}

public int NextInt()
{
var neg = false;
int res = 0;
SkipWhitespaces();
if ( !Eof && PeekNextChar() == '-' )
{
neg = true;
_pos++;
}
while ( !Eof && !IsWhitespace( PeekNextChar() ) )
{
var c = NextChar();
if ( c < '0' || c > '9' ) throw new ArgumentException( "Illegal character" );
res = 10 * res + c - '0';
}
return neg ? -res : res;
}

public int[] NextIntArray( int n )
{
var res = new int[n];
for ( int i = 0; i < n; i++ )
{
res[i] = NextInt();
}
return res;
}

public long NextLong()
{
var neg = false;
long res = 0;
SkipWhitespaces();
if ( !Eof && PeekNextChar() == '-' )
{
neg = true;
_pos++;
}
while ( !Eof && !IsWhitespace( PeekNextChar() ) )
{
var c = NextChar();
if ( c < '0' || c > '9' ) throw new ArgumentException( "Illegal character" );
res = 10 * res + c - '0';
}
return neg ? -res : res;
}

public long[] NextLongArray( int n )
{
var res = new long[n];
for ( int i = 0; i < n; i++ )
{
res[i] = NextLong();
}
return res;
}

public string NextLine()
{
SkipUntilNextLine();
if ( Eof ) return "";
var builder = new System.Text.StringBuilder();
while ( !Eof && !IsEndOfLine( PeekNextChar() ) )
{
builder.Append( NextChar() );
}
return builder.ToString();
}

public double NextDouble()
{
SkipWhitespaces();
var builder = new System.Text.StringBuilder();
while ( !Eof && !IsWhitespace( PeekNextChar() ) )
{
builder.Append( NextChar() );
}
return double.Parse( builder.ToString(), System.Globalization.CultureInfo.InvariantCulture );
}

public double[] NextDoubleArray( int n )
{
var res = new double[n];
for ( int i = 0; i < n; i++ )
{
res[i] = NextDouble();
}
return res;
}

public string NextToken()
{
SkipWhitespaces();
var builder = new System.Text.StringBuilder();
while ( !Eof && !IsWhitespace( PeekNextChar() ) )
{
builder.Append( NextChar() );
}
return builder.ToString();
}

private void SkipWhitespaces()
{
while ( !Eof && IsWhitespace( PeekNextChar() ) )
{
++_pos;
}
}

private void SkipUntilNextLine()
{
while ( !Eof && IsEndOfLine( PeekNextChar() ) )
{
++_pos;
}
}

private static bool IsWhitespace( char c )
{
return c == ' ' || c == '\t' || c == '\n' || c == '\r';
}

private static bool IsEndOfLine( char c )
{
return c == '\n' || c == '\r';
}

#endregion
}
}```

Attempt Ema’s Supercomputer HackerRank Challenge

Next HackerRank Challenge Solution