'''
python 2.7
consider a 2D matrix of numbers from 0 to 9 with
variable witdth and height. find the square
submatrix with the highest sum of boundary elements.
Input:
input width and height of matrix : 6 8
Input matrix with numbers from 0 to 9
(get the input matrix of 8 rows and 6 columns)
2 0 6 1 2 5
1 0 5 0 1 3
3 0 1 2 4 1
0 1 3 1 1 9
4 1 0 8 5 2
0 1 0 1 2 3
6 5 3 1 0 2
0 0 1 6 0 4
input maximum width of square submatrix(for submatrix height and width
are same): e.g. 3
Output: this submatrix has the highest sum of their boundry elements from matrix
2 4 1
1 1 9 => 2 + 4 + 1 + 9 + 2 + 5 + 8 + 1 => 32
8 5 2
'''
from __future__ import print_function
import sys
from copy import copy,deepcopy
class Find_max_submatrix:
def __init__(self):
self.row = 0
self.column = 0
self.sub_row_col = 0
self.matrix = [[0 for col in range(self.column)] for row in range(self.row)] #2D matrix empty
self.max_sum = 0
#get the input values from user
def get_input(self):
try:
self.row,self.column,self.sub_row_col = [int(x) for x in raw_input('enter rows and columns and submatrix_row_col three int values').split()]
except ValueError:
raise("Enter the the three integer values")
sys.exit()
#which shows the values entered by user of default values otherwise
def show_input(self):
print('row ' + str(self.row))
print('column '+ str(self.column))
print('sub_row_col '+ str(self.sub_row_col))
#set the matrix based on input values by user
def set_matrix(self):
if self.row < 1 or self.column < 1 or self.sub_row_col < 1:
raise("Value error for input matrix specify particular values")
sys.exit()
#if the input mismatches
if self.sub_row_col > self.row or self.sub_row_col > self.column:
raise("input mismatch error: enter submatrix less than or equal row and columns")
sys.exit()
print("Enter the Input matrix:")
#getting input here
self.matrix = [[int(elem) for elem in raw_input().split()]for row in range(self.row)]
#which shows the matrix
def show_matrix(self):
if self.matrix:
print('Original matrix:')
for i in range(self.row):
for j in range(self.column):
print(self.matrix[i][j],end=' ')#print each element by space
print() #for new line
def set_max_submatrix(self):
self.max_submatrix = deepcopy(self.submatrix)
def show_max_submatrix(self):
for i in range(self.sub_row_col):
for j in range(self.sub_row_col):
print(self.max_submatrix[i][j],end =' ')
print()
def get_max_submatrix(self):
for i in range(self.row - self.sub_row_col + 1 ):
for j in range(self.column - self.sub_row_col + 1):
self.set_submatrix(i,j)
#self.show_submatrix()
submatrix_sum = self.sum_submatrix()
print(submatrix_sum)
if self.max_sum < submatrix_sum:
self.set_max_submatrix()
self.max_sum = submatrix_sum
#returns the submatrix
def set_submatrix(self,row,col):
self.submatrix = [[self.matrix[i][j] for j in range(col,col + self.sub_row_col)]for i in range(row,row + self.sub_row_col)]
return self.submatrix
def show_submatrix(self):
for i in range(self.sub_row_col):
for j in range(self.sub_row_col):
print(self.submatrix[i][j],end =' ')
print()
#add the corner elements of submatrix
def sum_submatrix(self):
submatrix_sum = 0
for i in range(self.sub_row_col):
for j in range(self.sub_row_col):
#first and last row
if i == 0 or i == self.sub_row_col - 1:
submatrix_sum += self.submatrix[i][j]
else:
#middle rows if encountered first and last element
if j == 0 or j == self.sub_row_col - 1:
submatrix_sum += self.submatrix[i][j]
return submatrix_sum
if __name__ == '__main__':
submax = Find_max_submatrix()
submax.get_input()
submax.set_matrix()
## submax.show_matrix()
submax.get_max_submatrix()
## submax.show_submatrix()
submax.show_max_submatrix()
123
ReplyDelete