In The Sorting Game, you are given a
sequence containing a permutation of the integers between 1 and n, inclusive. In one move, you can take
any k consecutive elements of the
sequence and reverse their order. Find the fewest number of moves to sort the
sequence in ascending order.
Input. Consists of multiple test cases. The first
line of each test case contains two integers n (2 ≤ n ≤ 8)
and k (2 ≤ k ≤ n). The second
line of each test case contains a permutation of numbers from 1 to n.
Output. For each test case print in a separate
line the fewest number of moves to sort the sequence in ascending order or -1
if it's impossible.
Sample
input
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
Sample
output
0
1
7
-1
SOLUTION
graphs – breadth first search
Задачу будем решать при помощи поиска в
ширину. Сохраним исходную перестановку в массиве 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)
{
vector<int>
pos, p;
int i;
Начальную перестановку permut кладем в очередь и запускаем
поиск в ширину.
q.push_back(permut);
while(!q.empty())
{
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(i = 0;
i + k <= n; i++)
{
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;
}