Прямоугольник максимальной площали

Question

Я не могу понять как реализовать в коде нижеописанные действия. Использую язык Python.

Дана матрица состоящая только из чисел 1, 2, 3, 4.

Пример матрицы:

matrix = [[1, 4, 3, 4, 4, 1],
          [2, 3, 4, 2, 3, 1],
          [1, 4, 3, 2, 4, 1],
          [2, 3, 4, 2, 3, 4],
          [4, 3, 3, 1, 2, 4]]

Нужно найти прямоугольник максимальной площади, у которого угловые элементы равны числу, введённому с клавиатуры. На экран выводится площадь S и координаты левого нижнего и правого верхнего угла найденного прямоугольника.

Заранее спасибо за уделённое внимание.

Вот мои наработки:

line = 5
column = 6
i = 0
j = 0
c = 1
count = 0
num = int(input('Enter the number of quality: '))
l_up_cor = 0
r_up_cor = 0
l_up = 0
r_up = 0

for i in range(line):
for j in range(column):
    if j >= column-1:
        continue
    if i >= line-1:
        continue
    if l_up != 0 and r_up != 0:
        break
    if matrix[i][j] == num:
        if l_up != 0:
            continue
        else:
            l_up_cor = [i, j]
            l_up = matrix[i][j]
    if c >= column:
        c = 0
    else:
        if matrix[i][-c] == num:
            if r_up != 0:
                continue
            else:
                r_up_cor = [i, -c]
                r_up = matrix[i][-c]
        else:
            c += 1
c = 1
flag = False
for i in range(line):
    for j in range(column):
        if i <= line:
            if l_up_cor[0] == r_up_cor[0]:
                if matrix[l_up_cor[0]+c][l_up_cor[1]] == matrix[r_up_cor[0]+c][r_up_cor[1]] and matrix[l_up_cor[0]+c][l_up_cor[1]] == l_up:
                    print('rectangle')
                    matrix[r_up_cor[0] + c][r_up_cor[1]] = '*'
                    matrix[l_up_cor[0] + c][l_up_cor[1]] = '*'
                    flag = True
                    break
                else:
                    continue
            c += 1
    if flag:
        break

Answer 1

На базовом уровне достаточно обойти все возможные левые верхние углы, для каждого из них найти правые нижние (оптимизация - не хуже текущего лучшего решения), для каждой пары проверить наличие верхнего правого и нижнего левого.

Answer 2

Раз появились свои наработки (наконец-то) то приведу свое решение. У меня вроде получилось короче

smax=0
imax=-1
jmax=-1
lmax=-1
mmax=-1
pattern=int(input('Введите число'))
N=len(matrix)
M=len(matrix[0])
for i in range (N):
    for j in range (M):
        if matrix[i][j]==pattern :
            for l in range (i+1,N):
                for m in range (j+1,M):
                    if  matrix[i][j] == matrix[l][j] and matrix[i][j] == matrix[i][m] and  matrix[i][j] == matrix[l][m] :
                        s=(l-i)*(m-j)
                        if s>smax:
                            imax=i
                            jmax=j
                            lmax=l
                            mmax=m
                            smax=s
if smax==0:
    print ('Прямоугольников не найдено')
else:
    print (imax,jmax,lmax,mmax,matrix[imax][jmax],smax)

и результаты работы

Введите число 1
0 0 2 5 1 10
Введите число2
1 0 3 3 2 6
Введите число3
1 1 3 4 3 6
Введите число 4
0 1 2 4 4 6

БЛОГ НА HUSL

Прямоугольник максимальной площали

Ответы (2 шт):