После регионального этапа всероссийской олимпиады школьников по программированию пришлось услышать много хейта, что задача B-1 про короля — "глина", что написание 400 строк кода заняло три часа и всё равно не принесло 100 баллов и т.д. Поэтому я решил написать решение этой задачи сам и показать его вам. Да-да, я не писал решение этой задачи раньше.

Оказалось также, что опубликованный разбор этой задачи не самый простой, у задачи есть решение лучше, которое я вам и расскажу.

1. Нужно не строить маршрут короля, проходящий через заданный отрезок, а, наоборот, построить разные маршруты короля, содержащие все возможные отрезки (то есть все горизональные и все вертикальные), и выбрать тот маршрут, который содержит заданный отрезок.
2. Принципиально разных маршрутов всего два — это "змейка" для случая, когда обе стороны чётные, и когда одна сторона — чётная, а другая — нечётная. Все остальные конфигурации получаются отражением этой змейки относительно вертикальной или горизонтальной оси. Вот примеры двух змеек для этих случаев.
3. Такая змейка содержит почти все горизонтальные отрезки. Останутся только несколько отрезков у краёв доски, Но если эту змейку отразить относительно вертикальной или горизонтальной прямой, то можно будет покрыть все оставшиеся горизонтальные отрезки. А аналогичная змейка, но с длинными вертикальным линиями, также вместе с отражениями, покроет все вертикальные отрезки.
4. Поэтому существенная функция построения змейки в решении будет одна. Ещё объединим в общий код построение общей части змеек для чётного и нечётного числа строк. Различие двух случает будет только в построении одной последней строки для чётного числа строк и двух последних строк для нечётного числа строк. Все остальные преобразования змеек сделаем функциями преобразования таблицы: вертикальные и горизонтальные отражения, а также функция транспонирования матрицы, при помощи которой из змейки с горизонтальными линиями можно будет получить змейку с вертикальными линиями.

Также мне показалось, что удобней не хранить змейку в виде последовательности клеток, как это требуется при выводе ответа, а заполнить двумерный массив n*m числами, обозначающими номера клеток в порядке их обхода. Так проще строить змейку и выполнять последующие преобразования. А уже при выводе ответа вывести его в виде последовательности клеток.

В результате получился код на 90 строк на питоне, из них непустых строк — 71. Наверняка можно что-то ещё упростить, например, сделать функцию snake построения змейки более элегантной.

import sys

def snake(n, m):
    a = [[-1] * m for i in range(n)]
    x, y = 0, 0
    for val in range(n * m):
        a[x][y] = val
        val += 1
        if x == 0 and y == 0:
            y += 1
        elif y == 0:
            x -=1
        elif n % 2 == 0 and x == n - 1:
            y -= 1
        elif n % 2 == 1 and x == n - 1:
            if y % 2 == 1:
                y -= 1
            else:
                x -= 1
        elif n % 2 == 1 and x == n - 2:
            if y % 2 == 1:
                x += 1
            else:
                y -= 1
        elif y == m - 1 and x % 2 == 0:
            x += 1
        elif y == 1 and x % 2 == 1:
            x += 1
        elif x % 2 == 0:
            y += 1
        elif x % 2 == 1:
            y -= 1
    return a


def rot(a):
    return [[a[j][i] for j in range(len(a))] for i in range(len(a[0]))]


def flip1(a):
    for i in range(len(a) // 2):
        a[i], a[-1 - i] = a[-1 - i], a[i]


def flip2(a):
    for i in range(len(a)):
        a[i] = a[i][::-1]


def print_ans(a):
    ans = [""] * (n * m + 1)
    for x in range(n):
        for y in range(m):
            ans[a[x][y]] = str(x + 1) + " " + str(y + 1)
    ans[-1] = ans[0]
    print("\n".join(ans))
    sys.exit(0)


def check(a):
    v1 = a[x1][y1]
    v2 = a[x2][y2]
    if abs(v1 - v2) == 1 or abs(v1 - v2) == n * m - 1:
        print_ans(a)


n, m = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1

if n * m % 2 == 1:
    print(-1)
    sys.exit(0)

for a in (snake(n, m), rot(snake(m, n))):
    check(a)
    flip1(a)
    check(a)
    flip2(a)
    check(a)
    flip1(a)
    check(a)
print(-1)

Написание этого кода заняло менее часа. Первый сабмит принёс 88 баллов, оказалось, была глупая опечатка при проверке условия n * m — нечётное. После исправления этой ошибки получилось 96 баллов, из-за TL на двух тестах (действительно, в задаче доска содержит до миллиона клеток, а в решении строится до 8 разных маршрутов, что для питона уже многовато). Но пересдача с использованием PyPy принесла 100 баллов. То есть фактически алгоритм был написан сразу без ошибок. Но ещё у меня была одна функция, печатающая всю доску со змейкой для отладки, она не вошла в этот код.

Какое место этой задачи в региональном этапе? В этой задаче есть конструктивная идея, если вы начнёте думать в направлении "а какие бы змейки мне построить, чтобы покрыть все горизонтальные и вертикальные отрезки", несложно к ней прийти. Также есть умение работать с преобразованием плоскости (отражения, повороты). Ну и наконец нужно аккуратно всё написать. Как вы видите, у этой задачи есть весьма короткое решение, которое можно реализовать за приемлемое время (примерно час). А остальное зависит от вас — те, кто умеет писать код хорошо, используют общие идеи, функции для реализации, получают несложное решение. Ну а если у вас код на 400 и больше строк с разбором массы случаев, то и времени это отнимет у вас куда больше, что скажется на итоговом балле.

Олимпиады по программированию — это не только знание каких-то алгоритмов, но и умение писать хороший, простой код. Задачи, которые приносят баллы тем, кто умеет хорошо программировать, но не требуют знания каких-либо алгоритмов, тоже нужны.