Я несколько раз просматривал ваш код, и если я правильно понял, вы отмечаете свои прямоугольники двумя разными угловыми маркерами. Извините, если мой ответ является скорее комментарием для разъяснения вашей позиции, чем реальным ответом.
Часть ответа:: если вы ищете подходящий алгоритм, рассмотрите алгоритм сканирования строк. Я нашел пример здесь @SO для "самого большого прямоугольного решения".
Мой вопрос к вам, что вы действительно ищете?
- лучший способ решить дилемму цикла for
- лучший язык для вашего алгоритма
- более быстрый алгоритм поиска прямоугольников
Я также должен отметить, что решение Пола и ваше решение дают разные результаты, потому что Полс предполагает, что углы отмечены одними и теми же значениями, а вы предполагаете, что углы отмечены двумя разными значениями!
Я нашел время и свободу, чтобы проиллюстрировать это уродливым сценарием c&p: он сравнивает оба алгоритма, создавая 2D-поле и заполняя его строчными символами в нижнем регистре, а углы превращает в символы в верхнем регистре.
from random import choice
from string import lowercase
from collections import defaultdict
from itertools import permutations
from copy import deepcopy
m,n = 20, 20
myarray = [[choice(lowercase) for x in xrange(m)] for y in xrange(n)]
def markcorners(i,j,i2,j2):
myarray[i][j] = myarray[i][j].upper()
myarray[i2][j] = myarray[i2][j].upper()
myarray[i2][j2] = myarray[i2][j2].upper()
myarray[i][j2] = myarray[i][j2].upper()
def printrect():
for row in myarray:
print ''.join(row)
print '*'*m
def paul_algo():
tally = defaultdict(list)
for i,row in enumerate(myarray):
for j,n in enumerate(row):
tally[n].append((i,j))
# look for rectangular quads in each list
for k,v in tally.items():
for quad in permutations(v,4):
# sort quad so that we can get rectangle corners
quad = sorted(quad)
(i1,j1),(i2,j2) = quad[0], quad[-1]
# slice out opposite corners to see if we have a rectangle
others = quad[1:3]
if [(i1,j2),(i2,j1)] == others:
markcorners(i1,j1,i2,j2)
def xavier_algo():
for i in xrange(m):
for j in xrange(n):
for i2 in xrange(i + 1, m):
for j2 in xrange(j + 1, n):
if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]:
markcorners(i,j,i2,j2)
savearray = deepcopy(myarray)
printrect()
xavier_algo()
printrect()
myarray = deepcopy(savearray)
paul_algo()
printrect()
person
Don Question
schedule
08.01.2012