class Result {
  /**
   * Finds the maximum product of areas of two non-overlapping plus shapes.
   */
  public static int twoPluses(List<String> grid) {
    int rows = grid.size();
    int cols = grid.get(0).length();
    List<Set<Integer>> pluses = new ArrayList<>();
    char[][] matrix = convertToMatrix(grid);
    int maxProduct = 0;

    // Identify all possible pluses
    for (int r = 0; r < rows; r++) {
      for (int c = 0; c < cols; c++) {
        if (matrix[r][c] == 'G') {
          int maxWingLength = findMaxWing(matrix, r, c);
          // Find and save all the pluses that shares the same center as smaller pluses might not overlap while bigger ones do
          for (int i = maxWingLength; i >= 0; i--) {
            pluses.add(getPlusCells(r, c, i, cols));
          }
        }
      }
    }
    // Check every pair of pluses. if they don't overlap, compare the product of them with the max product found up to that point.
    for (int i = 0; i < pluses.size(); i++) {
      for (int j = i + 1; j < pluses.size(); j++) {
        if (!hasOverlap(pluses.get(i), pluses.get(j))) {
          int product = pluses.get(i).size() * pluses.get(j).size();
          maxProduct = Math.max(maxProduct, product);
        }
      }
    }
    return maxProduct;
  }

  /**
   * Determines the maximum wing length of a plus centered at the given cell. Checks each direction.
   */
  private static int findMaxWing(char[][] matrix, int row, int col) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int maxWing = 0;

    while (row - maxWing >= 0 && row + maxWing < rows && col - maxWing >= 0
        && col + maxWing < cols && matrix[row - maxWing][col] == 'G'
        && matrix[row + maxWing][col] == 'G'
        && matrix[row][col - maxWing] == 'G'
        && matrix[row][col + maxWing] == 'G') {
      maxWing++;
    }
    return maxWing - 1;
  }

  /**
   * Converts the grid of strings into a 2D character array.
   */
  private static char[][] convertToMatrix(List<String> grid) {
    int rows = grid.size();
    int cols = grid.get(0).length();
    char[][] matrix = new char[rows][cols];

    for (int r = 0; r < rows; r++) {
      matrix[r] = grid.get(r).toCharArray();
    }
    return matrix;
  }

  /**
   * Returns the set of cell indices covered by a plus with the given center and
   * wing length.
   */
  private static Set<Integer> getPlusCells(
      int row, int col, int wingLength, int cols) {
    Set<Integer> cells = new HashSet<>();
    cells.add(row * cols + col); // Center cell

    for (int i = 1; i <= wingLength; i++) {
      cells.add((row - i) * cols + col); // Up
      cells.add((row + i) * cols + col); // Down
      cells.add(row * cols + (col - i)); // Left
      cells.add(row * cols + (col + i)); // Right
    }
    return cells;
  }

  /**
   * Checks if two pluses overlap.
   */
  private static boolean hasOverlap(Set<Integer> plus1, Set<Integer> plus2) {
    for (int cell : plus1) {
      if (plus2.contains(cell)) {
        return true;
      }
    }
    return false;
  }
}