Алгоритмы: переставить 2D матрицу (с помощью элемента «переворачивание»)

Question

Меня интересует алгоритм, который решает следующее (эффективно): двумерную матрицу чисел [1..9], которую необходимо выровнять по горизонтальным линиям сверху (1) к низу (9), но только путем переворачивания вертикально или горизонтально с другим номером.

Пример входной матрицы: </p> <pre><code>1 8 2 6 1 6 9 2 5 1 6 2 3 6 9 2 9 8 5 1 7 4 2 8 4 2 7 6 9 5

Матрица желаемого выхода:

</p> <pre><code>1 1 1 1 2 2 2 2 2 2 3 4 4 5 5 5 6 6 6 6 6 7 7 8 8 8 9 9 9 9

Разъяснение по 'Flipping': возьмем, например, матрицу ввода. В верхнем левом углу есть «1». Эта 1 может либо перевернуться горизонтально с 8 рядом с ней (первая строка становится теперь 8 1 2 6 1 6 ), либо вертикально с 9 под ней (первая колонка становится теперь 9 1 3 5 4). Он не может перевернуться с 2 по диагонали.

Какие-нибудь решения (любой язык в порядке) этой проблемы?

Answer 1

хорошая головоломка! в любом случае, вы можете попробовать модифицированные версии алгоритмов сортировки. Я не слишком хорош в реализации, но я мог бы попытаться дать вам один позже. Другой способ решить эту проблему - алгоритм A *. это алгоритм поиска пути, используемый в искусственном интеллекте, но я видел, что он применим к проблеме, подобной этой.

Answer 2

Часть о невозможности перевернуть по диагонали - красная сельдь. (Просто переверните элемент рядом с ним, а затем под ним.) Таким образом, любой элемент может быть заменен на любой другой элемент в матрице повторными переворотами. Продолжите эту линию рассуждений, и вы увидите, что желаемое конечное состояние - это матрица, содержащая элементы в порядке возрастания, увеличиваясь слева направо и сверху вниз (как в вашем конечном состоянии).

Чтобы быстро получить этот конечный результат, просто измените исходную матрицу из двумерного массива в плоский список. Сортировать. Затем преобразуйте обратно в двумерный массив.

Если вам необходимо знать последовательность допустимых шагов, которые могут привести к конечному результату (обратите внимание, что такая последовательность не уникальна!), Следующий простой алгоритм сделает это:

1. Начните с позиционирования элемента, который принадлежит в верхнем левом углу; это текущая позиция.
2. Найдите минимальный элемент в оставшейся части матрицы.
3. Переверните этот элемент влево, пока он не достигнет столбца текущей позиции, затем вверх, пока он не достигнет строки текущей позиции.
4. Пометить текущую позицию как правильно размещенную.
5. Переместитесь в следующую позицию, сдвинув текущую позицию на один индекс вправо или в начало следующей строки, если была помещена вся строка.
6. Повторяйте, пока вся матрица не будет позиционирована.

Оптимально эффективно? Навряд ли. Просто и эффективно? Совершенно верно.