| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сортировка матрицы |
| Автор: Dashy 11.3.2007, 20:43 |
| Есть задача: дана матрица размером N*N квадратов, каждый из которых раскрашен в произвольном порядке одним из следующих цветов: красным, синим, зеленым, желтым. Необходимо за минимальное кол-во тактов переставить квадраты в матрице т. о., чтобы квадрат каждого цвета хотя бы одной гранью соприкасался с квадратом того же цвета, а в углах матрицы находились, начиная с левого верхнего, квадраты перечисленных цветов. Может кто знает, как это сделать? какой получается алгоритм? |
| Автор: Prof_2000 11.3.2007, 23:56 |
| Тактом считается перестановка двух соседних квадратов, или просто необходимо обеспечить наименьшую сложность алгоритма? Если второе - то просто считаем количество квадратов каждого из цветов и заполняем всю матрицу начиная с углов квадратами нужных цветов. Иначе - дело обстоит сложнее. Тогда, как я понимаю, необходимо писать динамику. Потому как рекурсия - слишком жирно, жадность работать не будет... Dashy, мне было б интересно вспомнить молодость и написать эту динамику, но для начала нужно быть уверенным, что я правильно понял условие. Поясните. |
| Автор: Dashy 12.3.2007, 19:48 |
| Тактом считается перестановка двух соседних квадратов. |