Advertisement
Guest User

Untitled

a guest
Nov 18th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.39 KB | None | 0 0
  1. import sys
  2.  
  3. class Stack:
  4.     def __init__(self):
  5.         self.items = []
  6.     def empty(self):
  7.         return self.size() == 0
  8.     def size(self):
  9.         return len(self.items)
  10.     def push(self, item):
  11.         self.items += [item] #another way to append
  12.     def pop(self):
  13.         return self.items.pop()
  14.     def top(self):
  15.         return self.items[-1]
  16.  
  17.  
  18. matrix = []
  19. #f = open(sys.argv[1],'r')
  20. f = open('rectangle3.txt', 'r')
  21. for line in f:
  22.     matrix.append(list(map(int, line.split())))
  23.  
  24. row = len(matrix)
  25. col = len(matrix[0])
  26. St = Stack()
  27.  
  28. def odd(x):
  29.     if x % 2 != 0:
  30.         return True
  31.     return False
  32.  
  33. for i in range(row):
  34.     for j in range(col):
  35.         if odd(matrix[i][j]):
  36.             matrix[i][j] = 1
  37.         else:
  38.             matrix[i][j] = 0
  39. for l in matrix:
  40.     print(l)
  41. print()
  42. def largestArea(arr, lenght):
  43.     area = []
  44.     items = []
  45.     for i in range(lenght):
  46.         area.append(0)
  47.  
  48.     for i in range(lenght):
  49.         while(items):
  50.             if (arr[i] <= arr[items[-1]]):
  51.                 items.pop()
  52.             else:
  53.                 break
  54.         if not St.items:
  55.             t = -1
  56.         else:
  57.             t = items[-1]
  58.         area[i] = i - t - 1
  59.         #print(area[i], end = ' ')
  60.         items.append(i)
  61.         #print(area)
  62.  
  63.     while (items):
  64.         items.pop()
  65.  
  66.     for i in range(lenght-1, -1, -1):
  67.         while (items):
  68.             if (arr[i] <= arr[items[-1]]):
  69.                items.pop()
  70.             else:
  71.                 break
  72.  
  73.         if not St.items:
  74.             t = lenght
  75.         else:
  76.             t = items[-1]
  77.         area[i] += t - i - 1
  78.         #print(area[i], end = ' ')
  79.         items.append(i)
  80.  
  81.     maxim = 0
  82.     for i in range(lenght):
  83.         area[i] = arr[i] * (area[i] + 1)
  84.         if area[i] > maxim:
  85.             maxim = area[i]
  86.     print(area)
  87.     return maxim
  88.  
  89. def find_max_matrix(A):
  90.     cur_maxim = 0
  91.  
  92.     for i in range(1, row):
  93.         for j in range(col):
  94.             if A[i][j] == 1:
  95.                 A[i][j] = A[i-1][j] + 1
  96.  
  97.  
  98.     for i in range(row):
  99.         maxim = largestArea(A[i], col)
  100.         #print(maxim, end = ' ')
  101.         if maxim > cur_maxim:
  102.             cur_maxim = maxim
  103.     for i in range(row-1, 0, -1):
  104.         for j in range(col):
  105.             if A[i][j]:
  106.                 A[i][j] = A[i][j] - A[i-1][j]
  107.  
  108.     return cur_maxim
  109.  
  110. print(find_max_matrix(matrix))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement