Loading...
dead4y avatar dead4y 62 Точки

Проблем със задача от Java lab : Largest Rectangle

Здравейте колеги, може ли малко помощ. Става на въпрос за https://judge.softuni.bg/Contests/131/Java-Fundamentals-Lab-October-27 този лаб.

На задачата Largest Rectangle изкарвам бедните 60 точки. Някой има ли идея къде може да ми е грешката? http://pastebin.com/NQnNaxDk

0
Java Advanced 27/10/2015 20:21:29
Innos avatar Innos 419 Точки
Best Answer

Това беше един от по-зачуканите проблеми които съм срещал колега, но го разгадах. Първо обаче има бая неща в кода ти които трябва да се засегнат. Първо както каза колегата имаш проблем със получаването на информация от входа, едно примерно решение на този проблем е да подмениш всички запетайки със спейсове и да тримнеш, или алтернативно да използваш стриимове ако знаеш как. Второ и циклите и пресмятането на площта на правоъгълника ти са грешни.
int y1 = 0; y1 < matrix.size() - 1;
int x1 = 0; x1 < matrix.get(y1).length - 1;
int y2 = y1 + 1; y2 < matrix.size();
int x2 = x1 + 1; x2 < matrix.get(y2).length;
по начина по който си ги декларирал се приема че y1 е началният ти ред x1 е началната ти колона, а y2 и x2 са ти съответно крайният ред и крайната колона. В момента обаче цикъла който обхожда началните редове ще върви от 1(0вият индекс)вия ред до предпоследния, цикъла за началните колони също. Друго което трябва да се засегне е че циклите за крайните колони и редове трябва да започват от текущият ред и колона (не от следващият), за да може да се образува правоъгълник с големина 1х1 който да е точно 1 клетка. Трябва да изглеждат така:

int y1 = 0; y1 < matrix.size() ;
int x1 = 0; x1 < matrix.get(y1).length;
int y2 = y1; y2 < matrix.size();
int x2 = x1; x2 < matrix.get(y2).length;

Площта от своя страна е равна на крайният ред - началният ред + 1 (не +1 за всеки ред) примерно нека приемем случая където началният ни ред е 0 крайният е 4, началната колона е 1 а крайната е 6 (примера от условието), площта на този правоъгълник тогава е (4(последен ред) - 0(начален ред) +1) * (6(последна колона) - 1(първа колона) + 1) => 5 * 6 = 30. Реалистично за самата ти програма това няма много значение мисля, тъй като всичките ти получени размери ще са грешни с еднаква разлика, но ако площта се изискваше щеше да гърми.

Главният ти проблем обаче е доста добре скрит и се крие в метода markCells и се проявява точно в по горно посоченият случай когато най-големият правоъгълник е с размер 1 клетка:

for (int i = x1; i <= x2; i++) {

            matrix.get(y1)[i] = "[" + matrix.get(y1)[i] + "]";

            matrix.get(y2)[i] = "[" + matrix.get(y2)[i] + "]";

        }

 

        for (int i = y1 + 1; i < y2; i++) {

            matrix.get(i)[x1] = "[" + matrix.get(i)[x1] + "]";

            matrix.get(i)[x2] = "[" + matrix.get(i)[x2] + "]";

        }

тогава става следното, нека кажем че клетката 1,1 = "ааа" е резултатът ни, x1 = 1, x2=1, y1 = 1, y2 = 1, тогава първият ред от цикъла ще мине и ще смени клетката на x1,y1(1,1) във "[aaa]", след това вторият ред ще мине и ще смени клетката на x1,y2(1,1 пак) във "[[aaa]]". Това са ти проблемите общо взето ако ги оправиш изкарва 100/100. Но отделно мога да ти предложа няколко съвета, които се надявам да ти помогнат да се ориентираш по лесно в задачи от този тип. Вместо да използваш масив със стойности за да си подаваш параметрите, подавай директно параметрите, ако параметрите също са добре наименувани ще ти е много по лесно да следиш какво точно се случва. Ако някоя променлива ще ти трябва да се достъпва от много методи, вместо да я размяташ наляво надясно може да я деклрарираш като статична така всички медоти в класа ще я виждат, без да трябва да им се подава.

4
28/10/2015 18:39:38
dead4y avatar dead4y 62 Точки

Благодаря колега, било е толкова просто а изобщо не съм обърнал внимание. Понеже ме мързеше да преправям целия код, реших да добавя едни проверки за пълненето (последните 2 фор цикъла) и изкарах 100/100. Ето кода крайния код http://pastebin.com/HLF5RfTN

П.С: Дължа ви и на двамата по 1 бира :д

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