[C# Sample Exam 13.06] Problem 2. Jedi Galaxy
Здравейте колеги!
Имам поблем с намемирането на оптимизирано решение на тази задача и под оптимизирано имам предвид без нито една излишна итерация.
На кратко това което правя е да намеря диагоналите по, които Иво и злата Сила се движат като използвам формулката от проблема от отвореният курс по Алгоритми - Eight Qeens. След това използвам един бърз while, който да ми намери най-първата клетка от текущият диагонал, която е в матрицата. Правя същото нещо и за двата диагонала. Нататък логиката продължава стандартно с един while, който се движи само по диагонала и в зависимост дали е Иво или злата Сила, събира или унищожава клетките през, които минава.
Проблемът: 0/100 точки в judge. Двата нулеви теста минават. Също така минават и комбинирано.
Моят код дава само грешни отговори. Застраховал съм се да не гърми никъде.
По-рано видях твоето решение. Аз точно това искам да избегна. Да не тръгвам от там където са ми зададени координатите, защото това може да е много извън матрицата.
До колкото разбирам от условието трябва да се обходи целият диагонал независимо къде са подадени координатите. Ами ако те са вътре в матрицата това значи, че трябва да се обходи освен от дадената клетка нагоре, също така и на доло.
Знам, че съм си ослужнил работата, но целта ми е перформънс, да не излизам от рамката на матрицата.
Не можеш ли да Min()-неш дадения координат и border-а на матрицата и да почнеш от там?
Първоначално го бях направила така -
int currentRow = evilStartRow < 0 ? 0: evilStartRow ;
intcurrentCol = evilStartCol < 0 ? 0: evilStartCol;
Ако се вървеше само по вертикала и хоризонтала да, но за да хвана диагонала с Min() поне аз не мога да си го представя.
Ти проверяваш само данните, които ти подават на входа дали са в матрицата, ако едната ти е -1 например, я правиш да е 0, и после вървиш по диагонала, като само си следиш да не излезеш от матрицата, докато вървиш нагоре.
Фейсбука умря :)
та като имаш 5-та колона, вадиш 1, и така вземаш 4-ти ред , -2 ти става 0, и те нали ти казват в условието, че иво винаги върви от долу ляво към горе дясно, а дявола върви от долу дясно само нагоре по диагонал наляво.
Където и да е началото на диагонала на Иво се взимат стойностите само нагоре, същото се отнася и за диагонала на злата сила.
Демек ако клетката ти се пада в центъра на матрицата тръгваш само нагоре по диагонала и забравяш за диагонала надолу от клетката, така ли?
Точна така
Ами надявам се качат тестовете на задачката, че ми стана много любопитно.
Това е моето решение - дава 70 от 100 точки. Цяла вечер се опитвам да си разбера проблема с останалите 30 точки. Може ли за помощ. Благодаря
http://pastebin.com/AZfYEQua
В методът където проверяваш дали клетката е в матрицата подаваш като параметри int galaxyCol, int galaxyRow , а като ги използваш в Main метода си ги разменил galaxyRows,galaxyCols.
Благодаря!
Колеги, не ми става ясно едно нещо. В условието на задачата се казва: "The given columns will be valid integers in the range [MinInt32, MaxInt32]."
А в кода на vani4ka66 правим следната проверка:
С тази проверка в While цикъла за ivoCol ние изключваме input от задачата с координати от сорта на 5 -100, което е извън матрицата, но по условие е позволено.
А това ни е 2-рата проверка:
Тук с проверката, която правим на evilCol (evilCol >= 0) отново изключваме input с координати, колона -N.
Не разбирам, защо е направено по този начин. В условието се казва, че единият диагонал(на Иво) започва от "from the lowest left to the upper right", а на Evil от " From lowest right to the upper left. ".
Constraints ни покриват row:
- The given rows will be valid integers in the range [0, 2000].
Но не и col, както вече споменах, а ние го ограничаваме собственоръчно при проверката.
Не разбирам защо е така. Някой може ли да ми обясни?
Не знам дали правилно съм разбрала въпроса ти, но ти трябва да провериш само данните, които ти подават на входа дали са в матрицата, ако едната ти е -1 например, я правиш да е 0, и после вървиш по диагонала, като само си следиш да не излезеш от матрицата, докато вървиш нагоре.
int currentRow = evilStartRow < 0 ? 0: evilStartRow ;
intcurrentCol = evilStartCol < 0 ? 0: evilStartCol;
Да но ти тази if проверка с тернарният оператор, не я правиш в кода тук
https://github.com/vani4ka66/Melrah-Shake/blob/master/Jedi%20Galaxy
Ами предполагам, че дори и да ти подадат отрицателно число за колоната на Иво, ivoStartCol докато е по-малка стойност от cols, ще се върти цикъла, и на всяка итерация ivoStartCol ще се увеличава с едно, докато попадне в матрицата и не се изпълни проверката в цикъла.
Тъй като се разбрахме във ФБ, само да добавя за някой друг ако чете. Стигнахме до извода, че условието на задачата не е написано както трябва и е некоректно, защото колоната пише че може да е пълният диапазон на Int32, а матрицата е с размери 5, 2000 макс, което може да доведе до input по-голям от матрицата, при който няма да влезе в while цикъла, така както е написано. Интересното е че минава 100/100, което означава грешно условие на задачата...