В Сортирующей Игре
изначально задана перестановка чисел от 1 до n включительно. За один ход можно выбрать любые k последовательно стоящих чисел и
развернуть их в
обратном порядке. Найти наименьшее количество
ходов, за которое можно отсортировать все числа в порядке возрастания.
Вход. Состоит из нескольких тестов. Первая строка каждого теста
содержит два целых числа n (2 ≤
n ≤ 8) и k (2 ≤ k ≤ n). Вторая строка каждого теста содержит
перестановку чисел от 1 до n.
Выход. Для каждого теста вывести в отдельной строке наименьшее
количество ходов, за которое можно отсортировать все числа в порядке
возрастания. Если сортировка невозможна, то вывести -1.
|
Пример
входа |
Пример
выхода |
|
3 3 1 2 3 3 3 3 2 1 8 4 7 2 1 6 8 4
3 5 5 4 3 2 4 1 5 |
0 1 7 -1 |
РЕШЕНИЕ
графы - поиск в ширину
Задачу будем
решать при помощи поиска в ширину. Сохраним исходную перестановку в массиве board
и занесем в очередь поиска в ширину. После извлечения очередной перестановки из
очереди будем перебирать в ней все возможные k последовательно стоящих чисел, обращать их и класть в очередь.
Входную
перестановку будем хранить в массиве permut. В массив Sorted занесем числа от 1 до n
в порядке возрастания – это перестановка, которую следует получить. Для поиска
в ширину используем очередь перестановок q.
Отображение m хранит расстояние от начальной перестановки до текущей.
deque<vector<int> > q;
map<vector<int>,int> m;
vector<int> permut, Sorted;
Функция fewestMoves возвращает наименьшее количество ходов, за которое можно
отсортировать все числа в порядке возрастания.
int fewestMoves(void)
{
Начальную перестановку permut кладем
в очередь и запускаем поиск в ширину.
q.push_back(permut);
while(!q.empty())
{
vector<int> pos = q[0];
q.pop_front();
Если текущая перестановка pos уже отсортирована (равна Sorted), то
возвращаем m[pos] – наименьшее
количество ходов, за которое можно получить pos.
if (pos ==
Sorted) return m[pos];
Перебираем все возможные варианты k последовательно стоящих чисел (подпоследовательность p[i, …, i + k], где i + k
≤ n) и разворачиваем их. Если
полученная перестановка не встречалась ранее (не занесена в отображение m), то
вычисляем расстояние до нее (минимальное количество ходов, за которое ее можно
получить) и заносим в конец очереди.
for(int i = 0; i + k <= n; i++)
{
vector<int> p = pos;
reverse(p.begin() + i,p.begin() + i + k);
if
(m.count(p) == 0)
{
m[p] = m[pos] + 1;
q.push_back(p);
}
}
}
Если просмотрены все перестановки, но
отсортированная последовательность чисел не
получена, то возвращаем -1.
return -1;
}
Основная часть программы. Читаем входные данные. Строим
отсортированный массив Sorted.
while(scanf("%d
%d",&n,&k) == 2)
{
Sorted.clear(); permut.clear();
m.clear(); q.clear();
for(i = 0; i
< n; i++)
{
Sorted.push_back(i+1);
scanf("%d",&value);
permut.push_back(value);
}
Запускаем поиск в ширину и выводим
результат.
res = fewestMoves();
printf("%d\n",res);
}
Улучшенная реализация
Можно
значительно ускорить работу программы, изменив структуры хранения данных. При
поиске в ширину в очереди q будем хранить не перестановки в виде
массивов, а их коды – целые числа. Пусть id – код перестановки, полученной
в процессе поиска в ширину. Тогда m[id] хранит наименьшее количество
операций разворота, после выполнения которых можно получить из исходной
перестановки перестановку с кодом id. Исходная перестановка хранится в
массиве permut.
deque<int>
q;
map<int,int> m;
int permut[8];
Перестановку, заданную в массиве а, будем кодировать
целым n-цифровым числом. Код перестановки возвращается функцией ID.
int ID(int *a)
{
int id = 0;
for (int i = 0; i
< n; i++) id = id * 10 + a[i];
return id;
}
Код id преобразуется в массив mas (каждую цифру
числа id заносим в отдельную ячейку массива mas).
void getAarray(int id, int *mas)
{
for (int i = n - 1; i
>= 0; i--, id /= 10)
mas[i] = id % 10;
}
На вход функции fewestMoves подается перестановка permut
и значение k.
int fewestMoves(int *permut, int k)
{
int i, j, a[8], b[8];
q.clear(); m.clear();
Заносим в очередь q код входной перестановки permut.
q.push_back(ID(permut));
while(!q.empty())
{
Извлекаем код перестановки из головы очереди. Преобразуем ее
в массив a.
int id = q[0]; q.pop_front();
getAarray(id, a);
Проверим, не расположены ли элементы текущей перестановки в
возрастающем порядке. Если да, то останавливаем поиск и возвращаем искомое
наименьшее количество ходов, хранящееся в m[id].
for(i = 0; i < n; i++)
if (a[i] != i + 1) break;
if (i == n) return
m[id];
Совершаем все возможные развороты k рядом стоящих
чисел.
for(i = 0; i + k <= n; i++)
{
for(j = 0; j < n; j++) b[j] = a[j];
reverse(b + i, b + i + k);
int idB = ID(b);
if (m[idB] == 0)
{
m[idB] = m[id] + 1;
q.push_back(idB);
}
}
}
return -1;
}
Основная часть программы. Для каждого теста читаем входные
данные и выводим ответ.
while(scanf("%d %d",&n,&k)
== 2)
{
for(i = 0; i < n; i++)
scanf("%d",&permut[i]);
res = fewestMoves(permut,k);
printf("%d\n",res);
}