Advertisement
Guest User

Untitled

a guest
Oct 28th, 2015
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.46 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.replace(',', ' ').trim().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(); y1++) {
  32. for (int x1 = 0; x1 < matrix.get(y1).length; x1++) {
  33. for (int y2 = y1; y2 < matrix.size(); y2++) {
  34. for (int x2 = x1; 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.  
  63. //check if rectangle is valid (all cells have same value)
  64. static boolean isValidRectangle(int x1, int y1, int x2, int y2, ArrayList<String[]> matrix) {
  65.  
  66. String stringToCompare = matrix.get(y1)[x1];
  67.  
  68. for (int i = x1; i <= x2; i++) {
  69. if (!matrix.get(y1)[i].equals(stringToCompare) || !matrix.get(y2)[i].equals(stringToCompare))
  70. return false;
  71. }
  72.  
  73. for (int i = y1 + 1; i < y2; i++) {
  74. if (!matrix.get(i)[x1].equals(stringToCompare) || !matrix.get(i)[x2].equals(stringToCompare))
  75. return false;
  76. }
  77.  
  78. return true;
  79. }
  80.  
  81. //add square brackets to cells that are the largest reactangle
  82. static void markCells(int[] markedCellRectPos, ArrayList<String[]> matrix) {
  83. int x1, x2, y1, y2;
  84.  
  85. x1 = markedCellRectPos[0];
  86. x2 = markedCellRectPos[2];
  87. y1 = markedCellRectPos[1];
  88. y2 = markedCellRectPos[3];
  89.  
  90. for (int i = x1; i <= x2; i++) {
  91. matrix.get(y1)[i] = "[" + matrix.get(y1)[i] + "]";
  92.  
  93. if(y2 != y1)
  94. matrix.get(y2)[i] = "[" + matrix.get(y2)[i] + "]";
  95. }
  96.  
  97. for (int i = y1 + 1; i < y2; i++) {
  98. matrix.get(i)[x1] = "[" + matrix.get(i)[x1] + "]";
  99.  
  100. if(x2 != x1)
  101. matrix.get(i)[x2] = "[" + matrix.get(i)[x2] + "]";
  102. }
  103. }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement