Матч 397, Сортирующая игра (SortingGame)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

В Сортирующей Игре изначально задана перестановка чисел от 1 до n включительно. За один ход можно выбрать любые k последовательно стоящих чисел и развернуть их. Найти наименьшее количество ходов, за которое можно отсортировать все числа в порядке возрастания.

Класс: SortingGame

Метод: int fewestMoves(vector<int> board, int k)

Ограничения: board содержит от 2 до 8 элементов, board содержит перестановку чисел от 1 до n, где n – количество элементов в board, 2 £ k £ n.

Вход. Массив board, содержащий перестановку чисел от 1 до n.

Выход. Наименьшее количество ходов, за которое можно отсортировать числа. Если сортировка невозможна, то вернуть -1.

Пример входа

board	k
{1,2,3}	3
{3,2,1}	3
{7,2,1,6,8,4,3,5}	4
{3,2,4,1,5}	4

Пример выхода

0

1

7

-1

РЕШЕНИЕ

поиск в ширину

Задачу будем решать при помощи поиска в ширину. Исходную перестановку, заданную в массиве board, заносим в очередь поиска в ширину. После извлечения перестановки из очереди будем перебирать в ней все возможные k последовательно стоящих чисел, обращать их и класть в очередь. Отображение m хранит расстояние от исходной перестановки до отсортированной.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <deque>

#include <map>

#include <algorithm>

using namespace std;

deque<vector<int> > q;

map<vector<int>,int> m;

class SortingGame

{

public:

int fewestMoves(vector<int> board, int k)

{

vector<int> pos, p, Sorted;

int i, n = (int)board.size();

for(i = 1; i <= n; i++) Sorted.push_back(i);

q.push_back(board);

while(!q.empty())

{

pos = q[0];q.pop_front();

if (pos == Sorted) return m[pos];

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);

}

}

}

return -1;

}

};