Угощения коров
Коровы отпраздновали еще один знаменательный месяц рекордного производства молока. Таким образом каждая из них заработала особое угощение. Коровы полностью заполнили прямоугольник w * h в ожидании угощения.
Каждая корова обладает уникальным достоинством F[rc] (1 ≤ F[rc] ≤ 1000000) которое обозначает ее общий показатель производства молока. Фермер Джон считает, что было бы справедливо расставить приоритеты по раздаче угощений, в первую очередь вознаграждая коров с высокой продуктивностью. Он планирует пройти прямоугольное поле по строкам, начиная раздавать угощения коровам с начала строки 1, потом с начала строки 2 и так далее.
Фермер Джон считает, что было бы справедливо расставить приоритеты по раздаче угощений, в первую очередь вознаграждая коров с высокой продуктивностью. Он планирует пройти по прямоугольнику строку за строкой слева направо, выдавая угощения коровам в такой последовательности.
Он попросил коров реорганизовать себя так, чтобы коровы с лучшей продуктивностью были вознаграждены первыми. Коровы, однако, не очень хороши в организации. Они могут поменять местами две строки или два столбца своего формирования. Фермер Джон попросил их сделать все возможное, переместив лучшую корову в верхний левый угол (строка 1, столбец 1), следующую лучшую корову в ряду 1, столбец 2 (если возможно) и так далее. Конечно, коровы не могут полностью отсортировать себя, но они могут сделать все возможное, следуя такой эвристике:
определить порядок вознаграждения Фермера Джона:
найдите корову с самым высоким рейтингом. Поменяйте местами строки и столбцы, пока она не окажется в строке 1, столбце 1. Никогда не двигайте ее снова.
Потом выполняйте следующее правило до тех пор, пока можно переставить как можно больше коров:
Найдите следующую корову с самым высоким рейтингом. Поменяйте местами строки и столбцы (при этом не перемещая коров с более высоким рейтингом) так, чтобы переместить ее в наилучшее возможное место, которое все еще доступно (например, строка 1, столбец 2, если оно доступно, или строка 2, столбец 1, если в первой строке нет свободных слотов).
Например, рассмотрим множество из 3 * 4 коров:
Корова с рейтингом 99 явно имеет самый высокий рейтинг, расположим ее в левом верхнем углу. Для этого поменяем местами строки 1 и 2, затем поменяем местами столбцы 1 и 2 (или наоборот - ответ такой же):
Корова с рейтингом 11 должна быть вознаграждена как можно скорее после коровы с самым высоким рейтингом. Она сейчас в ячейке (3, 4) - в последней ячейке, которая будет вознаграждена. На этом этапе уже слишком поздно менять ее на первый ряд или даже на первый столбец. Ей нужно перейти в (2, 2), поменяв местами столбцы 2 и 4, а затем поменяв местами строки 2 и 3:
Корова с рейтингом 10 получает вознаграждение сразу после коровы с 11. Корова 9 уже вознаграждена. Корова с 8 присуждается сразу после коровы с 10. Корова с 7 получает вознаграждение сразу после коровы с 8. Корова с 6 уже вознаграждена. Корову с 5 лучше всего переместить в строку 3, столбец 2, но строки 1 и 2 заморожены, как и все столбцы. Таким образом, коровы 1, 4 и 5 не двигаются, и вторая диаграмма выше - "лучшее, что могут сделать коровы".
Реализуйте этот алгоритм для других прямоугольных массивов коров.
Входные данные
Первая строка содержит два целых числа w и h (1 ≤ w ≤ 25, 1 ≤ h ≤ 25). Каждая из следующих h строк содержит w целых чисел F[ic] (1 ≤ c ≤ w).
Выходные данные
Выведите h строк. Каждая строка содержит w целых чисел, задающих ряд коров в окончательном их расположении.