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

Knigt's tour - кое решение иска Judge?

Задача 3 от Greedy Алгоритми.

Задачата има много решения, но Judge иска определено.

Правя си матица int[size,size] . Непосетените клетки са с нули ( 0 ). Посетените са със съотвтетния номер на хода.

Преди всеки ход проверявам възможните следващи клетки (който са най-много 8) и ги оценявам с възможностите за ходове от тях.

Избирам клетката с най-малко възможни ходове. И тук идва проблема - когато са равни възможностите коя клетка се избира?

Без точки - Рекурсивно решение -> https://pastebin.com/auSYZ0pa

Някакви точки - Итеративно решение ->  https://pastebin.com/hdkqbqUC

Явно трябва в определена последователност да се обхождат клетките. Смених моята и от 33 стигнах 66 точки:

static int[] r = { 1, -1,  2,  1, -1, -2,  2, -2 };
static int[] c = { 2,  2,  1, -2, -2,  1, -1, -1 };

 

 

Тагове:
AtanasYordanov avatar AtanasYordanov 38 Точки
Best Answer

При мен минава 100/100 със тази последователност:

new int[]{1, -1, 1, -1, 2, 2, -2, -2};
new int[]{2, 2, -2, -2, 1, -1, 1, -1};

 

2
MartinBG avatar MartinBG 1154 Точки

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

 

        private static readonly List<int[]> Moves = new List<int[]>
        {
            new [] { +1, +2 },
            new [] { -1, +2 },
            new [] { +1, -2 },
            new [] { -1, -2 },
            new [] { +2, +1 },
            new [] { +2, -1 },
            new [] { -2, +1 },
            new [] { -2, -1 },
        };

 

2
butoff avatar butoff 33 Точки

Супер!

Разгадал си решението. Това е вярната последователност!

 

 

0
viraco4a avatar viraco4a 28 Точки

Ето още едно решение: https://pastebin.com/8H1jFb5p 

И ето последователността, която judge очаква (т.е. в коя посока в каква последователност се пробва да отиде конят, като разбира се ползвам Warnsdorf методът

1) RRD 

2) RRU

3) LLD 

4) LLU 

5) DDR 

6) DDL 

7) RUU

8) LUU 

2