Hello Programmers, In this post, you will know how to solve the HackerRank Emas Supercomputer Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Emas Supercomputer Game Solution
Task
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.
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 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.
Constraints
- 2 <= n <= 15
- 2 <= m <= 15
Output Format
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
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.
HackerRank Emas Supercomputer Solution
Emas Supercomputer 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; }
Emas Supercomputer Solution in Cpp
#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; }
Emas Supercomputer Solution in Java
import java.io.IOException; import java.util.Arrays; import java.util.Scanner; public class Solution { static boolean[][] good; public static void main(String[] args) throws IOException{ Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); good = new boolean[n][m]; for(int i = 0; i < n; i++) { String s = in.next(); for(int j = 0; j < m; j++) { good[i][j] = s.charAt(j) == 'G'; } } int s = 0; for(int a = 0; a < n; a++) { for(int b = 0; b < m; b++) { for(int c = 0; a - c >= 0 && a + c < n && b - c >= 0 && b + c < m; c++) { for(int x = 0; x < n; x++) { for(int y = 0; y < m; y++) { for(int z = 0; x - z >= 0 && x + z < n && y - z >= 0 && y + z < m; z++) { if(valid(a, b, c, x, y, z)) { s = Math.max(s, (4 * c + 1) * (4 * z + 1)); } } } } } } } System.out.println(s); } public static boolean valid(int a, int b, int c, int x, int y, int z) { boolean[][] cp = new boolean[good.length][good[0].length]; for(int i = 0; i < good.length; i++) { for(int j = 0 ; j < good[0].length; j++) { cp[i][j] = good[i][j]; } } if(!cp[a][b]) { return false; } cp[a][b] = false; for(int i = 1; i <= c; i++) { if(!cp[a - i][b] || !cp[a][b - i] || !cp[a + i][b] || !cp[a][b + i]) { return false; } cp[a - i][b] = false; cp[a + i][b] = false; cp[a][b - i] = false; cp[a][b + i] = false; } if(!cp[x][y]) { return false; } cp[x][y] = false; for(int i = 1; i <= z; i++) { if(!cp[x - i][y] || !cp[x][y - i] || !cp[x + i][y] || !cp[x][y + i]) { return false; } cp[x - i][y] = false; cp[x + i][y] = false; cp[x][y - i] = false; cp[x][y + i] = false; } return true; } }
Emas Supercomputer Solution in Python
# Enter your code here. Read input from STDIN. Print output to STDOUT from sys import exit # read input ns = map(int, raw_input().strip().split()) n = ns[0] grid = [] for i in range(n): grid.append(raw_input()) # make sure there are at least 2 Gs, else output 0 num_gs = 0 for row in grid: num_gs += len(row) - len(row.replace("G", "")) if num_gs < 2: print 0 exit(0) grid = [list(x) for x in grid] # find pluses n stuff def get_max_plus_radius(g, r, c): left_bound = c while left_bound >= 0 and g[r][left_bound] == 'G': left_bound -= 1 right_bound = c while right_bound < len(g[r]) and g[r][right_bound] == 'G': right_bound += 1 upper_bound = r while upper_bound >= 0 and g[upper_bound][c] == 'G': upper_bound -= 1 lower_bound = r while lower_bound < len(g) and g[lower_bound][c] == 'G': lower_bound += 1 bound = min(c - left_bound, right_bound - c, r - upper_bound, lower_bound - r) return bound def get_area_with_radius(radius): return 1 + (radius - 1)*4 def get_max_plus_area_at(g, r, c): bound = get_max_plus_radius(g, r, c) if bound == 0: return 0 return get_area_with_radius(bound) def find_max_plus_area(g): max_plus_area = 0 for row in range(len(g)): for col in range(len(g[row])): max_plus_area = max(max_plus_area, get_max_plus_area_at(g, row, col)) return max_plus_area def set_plus_val(g, r, c, rad, val): left_cursor = c right_cursor = c up_cursor = r down_cursor = r while rad > 0: g[r][left_cursor] = val g[r][right_cursor] = val g[up_cursor][c] = val g[down_cursor][c] = val left_cursor-=1 right_cursor+=1 up_cursor-=1 down_cursor+=1 rad -= 1 max_area_product = 0 for row in range(len(grid)): for col in range(len(grid[row])): # for each plus centered at this location cur_max_rad = get_max_plus_radius(grid, row, col) for cur_rad in range(1, cur_max_rad+1): area1 = get_area_with_radius(cur_rad) set_plus_val(grid, row, col, cur_rad, 'B') area2 = find_max_plus_area(grid) max_area_product = max(max_area_product, area1*area2) set_plus_val(grid, row, col, cur_rad, 'G') print max_area_product
Emas Supercomputer Solution using JavaScript
function replaceChar(s, i, ch) { return s.substr(0, i) + ch + s.substr(i + ch.length); } function processData(input) { var lines = input.split("\n"); var nm = lines[0].split(" "), n = 1*nm[0], m = 1*nm[1]; var grid = lines.slice(1); function rank(grid, i, j) { for (var o = 1; o <= Math.min(i, j, n - 1 - i, m - 1 - j); o++) if (grid[i-o][j] === "B" || grid[i+o][j] === "B" || grid[i][j-o] === "B" || grid[i][j+o] === "B") break; return o; } function area(r) { return 4 * (r-1) + 1; } var maxprod = 0; for (var i = 0; i < n; i++) for (var j = 0; j < m; j++) if (grid[i][j] === "G") { var r = rank(grid, i, j); var ngrid = grid.concat(); ngrid[i] = replaceChar(ngrid[i], j, "B"); for (var o = 1; o < r; o++) { ngrid[i-o] = replaceChar(ngrid[i-o], j, "B"); ngrid[i+o] = replaceChar(ngrid[i+o], j, "B"); ngrid[i] = replaceChar(ngrid[i], j-o, "B"); ngrid[i] = replaceChar(ngrid[i], j+o, "B"); } var r2 = 0; for (var k = 0; k < n; k++) for (var l = 0; l < m; l++) if (ngrid[k][l] === "G") r2 = Math.max(r2, rank(ngrid, k, l)); maxprod = Math.max(maxprod, area(r)*area(r2)); } console.log(maxprod); } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); });
Emas Supercomputer Solution in Scala
object Solution { def main(args: Array[String]) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */ import scala.io.StdIn import scala.collection.mutable val lin = StdIn.readLine.split(' ').head.toInt val arr: Seq[Array[Char]] = Seq.fill(lin)(StdIn.readLine.toCharArray) type Plus = List[(Int, Int)] def createPossibles(lini: Int, coli: Int, step: Int): Option[Plus] = for { cent <- safeGet(lini, coli) left <- safeGet(lini - step, coli) up <- safeGet(lini, coli - step) right <- safeGet(lini + step, coli) down <- safeGet(lini, coli + step) inner <- if (step > 0) createPossibles(lini, coli, step - 1) else Some(Nil) } yield { (List(cent, left, up, right, down) ::: inner) .distinct } def safeGet(lini: Int, coli: Int): Option[(Int, Int)] = for { i <- arr.lift(lini) n <- i.lift(coli) if n == 'G' } yield (lini, coli) def findNext(step: Int): Seq[Plus] = for { (line, lini) <- arr.zipWithIndex (cole, coli) <- line.zipWithIndex plus <- createPossibles(lini, coli, step) } yield plus val allPluses = for (i <- 0 to lin) yield findNext(i) val withoutEMpty = allPluses.flatten.filter(_.nonEmpty) val startQu: mutable.Queue[Plus] = collection.mutable.Queue(withoutEMpty: _*) def compute(qu: mutable.Queue[Plus]): mutable.Queue[Int] = { val one = qu.dequeue() val answers: mutable.Queue[Int] = qu.collect { case two if (two intersect one).isEmpty => two.size * one.size case _ => 0 } if (qu.nonEmpty) { compute(qu) ++ answers } else answers } val max = compute(startQu).sorted.last println(max) } }
Emas Supercomputer Solution in Pascal
uses math; var n,m,res,count:longint; a:array[0..55,0..55] of char; c:array[0..55,0..55] of longint; Procedure ReadF; var i,j:longint; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do read(a[i,j]); readln; end; end; Procedure Process; var i,j,k,x,y,h:longint; begin count:=1; for i:=1 to n do for j:=1 to m do for k:=1 to 20 do if (a[i-k+1,j]=a[i+k-1,j]) and (a[i+k-1,j]=a[i,j-k+1]) and (a[i+k-1,j]=a[i,j+k-1]) and (a[i+k-1,j]='G') then begin c[i-k+1,j]:=1; c[i+k-1,j]:=1; c[i,j+k-1]:=1; c[i,j-k+1]:=1; for x:=1 to n do for y:=1 to m do for h:=1 to 20 do if (a[x-h+1,y]=a[x+h-1,y]) and (a[x+h-1,y]=a[x,y-h+1]) and (a[x+h-1,y]=a[x,y+h-1]) and (a[x+h-1,y]='G') and (c[x-h+1,y]<count) and (c[x+h-1,y]<count) and (c[x,y+h-1]<count) and (c[x,y-h+1]<count) then res:=max(res,((k-1)*4+1)*((h-1)*4+1)) else break; end else begin fillchar(c,sizeof(c),0); break; end; write(res); end; begin ReadF; Process; end.
Disclaimer: This problem (Emas Supercomputer) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.