Софтуерно Инженерство
Loading...
+ Нов въпрос
dead4y avatar dead4y 64 Точки

Проблем със задача от 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 SoftUni Team 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 64 Точки

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

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

1
penkov avatar penkov 110 Точки

Здравей, 

ако ти гърмят първите 4 теста, най-вероятно грешката е в това, че хващаш символи преди началната запетая а не трябва. Направи го със stream и trim. И би трябвало всичко да е точно!

0