Софтуерно Инженерство
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 };

 

 

Тагове:
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