Knigt's tour - кое решение иска Judge? - Софтуерен университет

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 };

Тагове:

30/03/2018 09:53:17 Структури от данни и алгоритми

AtanasYordanov 37 Точки

Best Answer

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

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

30/03/2018 10:09:37

MartinBG 4803 Точки

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

        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 },
        };

30/03/2018 10:07:51

butoff 33 Точки

Супер!

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

30/03/2018 10:19:15

viraco4a 28 Точки

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

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

1) RRD

2) RRU

3) LLD

4) LLU

5) DDR

6) DDL

7) RUU

8) LUU

31/03/2018 18:34:11