Софтуерно Инженерство
Loading...
zisov4eto avatar zisov4eto 19 Точки

[C# Sample Exam 13.06] Problem 2. Jedi Galaxy

Здравейте колеги!

Имам поблем с намемирането на оптимизирано решение на тази задача и под оптимизирано имам предвид без нито една излишна итерация.

На кратко това което правя е да намеря диагоналите по, които Иво и злата Сила се движат като използвам формулката от проблема от отвореният курс по Алгоритми - Eight Qeens. След това използвам един бърз while, който да ми намери най-първата клетка от текущият диагонал, която е в матрицата. Правя същото нещо и за двата диагонала. Нататък логиката продължава стандартно с един while, който се движи само по диагонала и в зависимост дали е Иво или злата Сила, събира или унищожава клетките през, които минава.

 

Проблемът: 0/100 точки в judge. Двата нулеви теста минават. Също така минават и комбинирано.

 

SOURSE CODE

Тагове:
0
C# Advanced 16/06/2016 15:50:12
vani4ka66 avatar vani4ka66 24 Точки

Много сложна си направил задачата. Понеже в момента не мога да видя къде гърми, ако искаш виж друго решение, според мен е доста оптимизирано!

 

https://github.com/vani4ka66/Melrah-Shake/blob/master/Jedi%20Galaxy

1
zisov4eto avatar zisov4eto 19 Точки

Моят код дава само грешни отговори. Застраховал съм се да не гърми никъде. 

 

По-рано видях твоето решение. Аз точно това искам да избегна. Да не тръгвам от там където са ми зададени координатите, защото това може да е много извън матрицата. 

 

До колкото разбирам от условието трябва да се обходи целият диагонал независимо къде са подадени координатите. Ами ако те са вътре в матрицата това значи, че трябва да се обходи освен от дадената клетка нагоре, също така и на доло. 

 

Знам, че съм си ослужнил работата, но целта ми е перформънс, да не излизам от рамката на матрицата. 

0
16/06/2016 17:16:03
RoYaL avatar RoYaL SoftUni Team Trainer 6883 Точки

Не можеш ли да Min()-неш дадения координат и border-а на матрицата и да почнеш от там?

1
vani4ka66 avatar vani4ka66 24 Точки

         Първоначално го бях направила така - 

 

                        int currentRow = evilStartRow  < 0 ? 0: evilStartRow ;
                        intcurrentCol = evilStartCol < 0 ? 0: evilStartCol;

 

 


 

0
zisov4eto avatar zisov4eto 19 Точки

Ако се вървеше само по вертикала и хоризонтала да, но за да хвана диагонала с Min() поне аз не мога да си го представя.

0
vani4ka66 avatar vani4ka66 24 Точки

Ти проверяваш само данните, които ти подават на входа дали са в матрицата, ако  едната ти е -1 например,  я правиш да е 0, и после вървиш по диагонала, като само си следиш да не излезеш от матрицата, докато вървиш нагоре. 

0
vani4ka66 avatar vani4ka66 24 Точки

Фейсбука умря :) 

та като имаш 5-та колона, вадиш 1, и така вземаш  4-ти ред , -2 ти става 0, и те нали ти казват в условието, че иво винаги върви от долу ляво към горе дясно, а дявола върви от долу дясно само нагоре по диагонал наляво. 

0
k_mitova avatar k_mitova 15 Точки

Където и да е началото на диагонала на Иво се взимат стойностите само нагоре, същото се отнася и за диагонала на злата сила. 

0
zisov4eto avatar zisov4eto 19 Точки

Демек ако клетката ти се пада в центъра на матрицата тръгваш само нагоре по диагонала и забравяш за диагонала надолу от клетката, така ли?

0
Ivanov.Ivan avatar Ivanov.Ivan SoftUni Team Trainer 557 Точки

Точна така

1
zisov4eto avatar zisov4eto 19 Точки

Ами надявам се качат тестовете на задачката, че ми стана много любопитно.

0
TihomirDimov avatar TihomirDimov 161 Точки

Това е моето решение - дава 70 от 100 точки. Цяла вечер се опитвам да си разбера проблема с останалите 30 точки. Може ли за помощ. Благодаря

http://pastebin.com/AZfYEQua

0
k_mitova avatar k_mitova 15 Точки

В методът където проверяваш дали клетката е в матрицата подаваш като параметри int galaxyCol, int galaxyRow , а като ги използваш в Main метода си ги разменил galaxyRows,galaxyCols.

1
12/08/2016 13:34:15
TihomirDimov avatar TihomirDimov 161 Точки

Благодаря!

0
sevdalin avatar sevdalin 37 Точки

Колеги, не ми става ясно едно нещо. В условието на задачата се казва: "The given columns will be valid integers in the range [MinInt32, MaxInt32]."

А в кода на vani4ka66 правим следната проверка:

        while (ivoRow >= 0 && ivoCol < matrix.GetLength(1))
        {
            if (IsInMatrix(ivoRow, ivoCol, matrix))
            {
                sum += matrix[ivoRow, ivoCol];
            }
            ivoRow--;
            ivoCol++;
        }

С тази проверка в While цикъла за ivoCol ние изключваме input от задачата с координати от сорта на 5 -100, което е извън матрицата, но по условие е позволено.

А това ни е 2-рата проверка:

        while (evilCol >= 0 && evilRow >= 0)
        {
            if (IsInMatrix(evilRow, evilCol, matrix))
            {
                matrix[evilRow, evilCol] = 0;
            }
            evilCol--;
            evilRow--;
        }

Тук с проверката, която правим на 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, както вече споменах, а ние го ограничаваме собственоръчно при проверката.

Не разбирам защо  е така. Някой може ли да ми обясни?

0
vani4ka66 avatar vani4ka66 24 Точки

Не знам дали правилно съм разбрала въпроса ти, но ти трябва да провериш само данните, които ти подават на входа дали са в матрицата, ако  едната ти е -1 например,  я правиш да е 0, и после вървиш по диагонала, като само си следиш да не излезеш от матрицата, докато вървиш нагоре.         

                        int currentRow = evilStartRow  < 0 ? 0: evilStartRow ;
                        intcurrentCol = evilStartCol < 0 ? 0: evilStartCol;

0
sevdalin avatar sevdalin 37 Точки

Да но ти тази if проверка с тернарният оператор, не я правиш в кода тук

https://github.com/vani4ka66/Melrah-Shake/blob/master/Jedi%20Galaxy

0
vani4ka66 avatar vani4ka66 24 Точки

Ами предполагам, че дори и да ти подадат отрицателно число за колоната на Иво, ivoStartCol докато е по-малка стойност от cols, ще се върти цикъла, и на всяка итерация ivoStartCol ще се увеличава с едно, докато попадне в матрицата и не се изпълни проверката в цикъла. 

 

while (ivoStartRow >= 0 && ivoStartCol < cols)
  {
  if (IsInMatrix(matrix, ivoStartRow, ivoStartCol))
  {
  sum += matrix[ivoStartRow, ivoStartCol];
  }
   
  ivoStartRow--;
  ivoStartCol++;
  }
0
sevdalin avatar sevdalin 37 Точки

Тъй като се разбрахме във ФБ, само да добавя за някой друг ако чете. Стигнахме до извода, че условието на задачата не е написано както трябва и е некоректно, защото колоната пише че може да е пълният диапазон на Int32, а матрицата е с размери 5, 2000 макс, което може да доведе до input по-голям от матрицата, при който няма да влезе в while цикъла, така както е написано. Интересното е че минава 100/100, което означава грешно условие на задачата...

1