[Exam Problems] PHP Basics 29 Аугуст 2014 Evening - Problem {3} - Largest Rectangle

Понеже тази задача предизвика доста дискусии по време на подготовката, реших да постна моето решение. Всъщност не е толкова трудна, колкото изглежда. Обхождаме всички възможни правоъгълници. Проверяваме всеки от тях дали е с еднакви символи по края. Ако отговаря на това условие смятаме лицето му и ако е най-големият до момента, пазим координатите му в асоциативен масив. Накрая печатаме матрицата, като проверяваме за всяка точка дали е в границите на конкретния правоъгълник. Ето кода:

http://pastebin.com/uWPtRk1a

Ако някой има въпроси, ще се радвам да помогна.

Приемаме, че стартовата точка на даден правоъгълник е неговия горен ляв ъгъл и представлява клетка в матрицата.

Минималният размер на матрицата е 1x1, значи минималният размер на всеки правоъгълник също е 1x1 и стартовата му точка може да бъде всяка една клетка в матрицата.

Максималната широчина / височина на всеки правоъгълник е разликата от широчината / височината на матрицата и стартовата му точка.

За всяка стартова точка проверяваме всички възможни широчини и за всяка широчина проверяваме всяка възможна височина.

Ако широчината е `n`, а височината - `m` :

Горната граница на правоъгълник я обикаляме като започнем от стартовата му точка и вървим `n` пъти надясно по матрицата, а долната граница я започваме от стартовата му точка + `m` и пак вървим `n` пъти надясно. Аналогично за лявата и дясната граница.

Моето решение

Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.

[Exam Problems] PHP Basics 29 Аугуст 2014 Evening - Problem {3} - Largest Rectangle