Advertisement
Guest User

Untitled

a guest
Oct 27th, 2015
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.38 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. public class LargestRectangle {
  5.     public static void main(String[] args) {
  6.         Scanner scanner = new Scanner(System.in);
  7.  
  8.         ArrayList<String[]> matrix = new ArrayList<>();
  9.  
  10.         String consoleInput = scanner.nextLine();
  11.  
  12.         //get input and fill in
  13.         while (!consoleInput.equals("END")) {
  14.  
  15.             String[] consoleInputArray = consoleInput.split(",");
  16.             String[] matrixRow = new String[consoleInputArray.length];
  17.  
  18.             for (int i = 0; i < consoleInputArray.length; i++) {
  19.                 matrixRow[i] = consoleInputArray[i];
  20.             }
  21.  
  22.             matrix.add(matrixRow);
  23.  
  24.             consoleInput = scanner.nextLine();
  25.         }
  26.  
  27.         int maxRectangleArea = 0;
  28.         int[] maxRectangleAreaAxes = new int[4];
  29.  
  30.         //get through all possible rectangles and if they are larger than previous found save its position
  31.         for (int y1 = 0; y1 < matrix.size() - 1; y1++) {
  32.             for (int x1 = 0; x1 < matrix.get(y1).length - 1; x1++) {
  33.                 for (int y2 = y1 + 1; y2 < matrix.size(); y2++) {
  34.                     for (int x2 = x1 + 1; x2 < matrix.get(y2).length; x2++) {
  35.  
  36.                         int[] rectanleAreaAxes = new int[] {x1, y1, x2, y2};
  37.                         int rectangleArea = (x2 + 1 - x1 + 1) * (y2 + 1 - y1 + 1);
  38.  
  39.                         if (isValidRectangle(rectanleAreaAxes[0], rectanleAreaAxes[1], rectanleAreaAxes[2], rectanleAreaAxes[3], matrix) && maxRectangleArea < rectangleArea) {
  40.                             maxRectangleArea = rectangleArea;
  41.                             maxRectangleAreaAxes = rectanleAreaAxes;
  42.                         }
  43.  
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.  
  49.  
  50.         markCells(maxRectangleAreaAxes, matrix);
  51.  
  52.         //print
  53.         for (int i = 0; i < matrix.size(); i++) {
  54.             for (int j = 0; j < matrix.get(i).length; j++) {
  55.                 System.out.printf("%5s", matrix.get(i)[j]);
  56.             }
  57.             System.out.println();
  58.         }
  59.  
  60.  
  61.     }
  62.     //check if rectangle is valid (all cells have same value)
  63.     static boolean isValidRectangle(int x1, int y1, int x2, int y2, ArrayList<String[]> matrix) {
  64.  
  65.         String stringToCompare = matrix.get(y1)[x1];
  66.  
  67.         for (int i = x1; i <= x2; i++) {
  68.             if (!matrix.get(y1)[i].equals(stringToCompare) || !matrix.get(y2)[i].equals(stringToCompare))
  69.                 return false;
  70.         }
  71.  
  72.         for (int i = y1 + 1; i < y2; i++) {
  73.             if (!matrix.get(i)[x1].equals(stringToCompare) || !matrix.get(i)[x2].equals(stringToCompare))
  74.                 return false;
  75.         }
  76.  
  77.         return true;
  78.     }
  79.  
  80.     //add square brackets to cells that are the largest reactangle
  81.     static void markCells(int[] markedCellRectPos, ArrayList<String[]> matrix) {
  82.         int x1, x2, y1, y2;
  83.  
  84.         x1 = markedCellRectPos[0];
  85.         x2 = markedCellRectPos[2];
  86.         y1 = markedCellRectPos[1];
  87.         y2 = markedCellRectPos[3];
  88.  
  89.         for (int i = x1; i <= x2; i++) {
  90.             matrix.get(y1)[i] = "[" + matrix.get(y1)[i] + "]";
  91.             matrix.get(y2)[i] = "[" + matrix.get(y2)[i] + "]";
  92.         }
  93.  
  94.         for (int i = y1 + 1; i < y2; i++) {
  95.             matrix.get(i)[x1] = "[" + matrix.get(i)[x1] + "]";
  96.             matrix.get(i)[x2] = "[" + matrix.get(i)[x2] + "]";
  97.         }
  98.     }
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement