Loading...
Hristo_Penchev avatar Hristo_Penchev 389 Точки

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

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

http://pastebin.com/uWPtRk1a

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

Тагове:
4
PHP Web Development Basics
AleksandurSeferinkin avatar AleksandurSeferinkin 333 Точки

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

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

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

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

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

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

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

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.