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 BufferedReader in;
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])) {
in = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
}
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()) {
line = new StringTokenizer(in.readLine());
}
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 System.Threading;
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));
Console.ReadLine();
#endif
}
static void Main()
{
new Solution().Start();
}
#endregion
}
}
namespace kp.Algo { }
namespace kp.Algo.IO
{
public class Scanner : IDisposable
{
#region Fields
readonly System.IO.TextReader _reader;
readonly int _bufferSize;
readonly bool _closeReader;
readonly char[] _buffer;
int _length, _pos;
#endregion
#region .ctors
public Scanner( System.IO.TextReader reader, int bufferSize, bool closeReader )
{
_reader = reader;
_bufferSize = bufferSize;
_closeReader = closeReader;
_buffer = new char[_bufferSize];
FillBuffer( false );
}
public Scanner( System.IO.TextReader reader, bool closeReader ) : this( reader, 1 << 16, closeReader ) { }
public Scanner( string fileName ) : this( new System.IO.StreamReader( fileName, System.Text.Encoding.Default ), true ) { }
#endregion
#region IDisposable Members
public void Dispose()
{
if ( _closeReader )
{
_reader.Close();
}
}
#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 )
{
_length = _reader.Read( _buffer, 0, _bufferSize );
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
Link – https://www.hackerrank.com/challenges/two-pluses/
Next HackerRank Challenge Solution
Link – https://exploringbits.com/larrys-array-hackerrank-solution/
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.
