Задание с графом

[Moctavius]

Добрый день. Есть задание с графом, где решение - обход графа в ширину. Но я вообще не понимаю как, даже с чего начать.
Даны числа:
8 4
7 2 1 6 8 4 3 5
3 3
3 2 1

Где в первой строке первое число - количество чисел, второе - кол-во последовательно идущих чисел, которое можно поставить в обратном порядке.
Для каждого такого набора нужно вывести наименьшее количество ходов, за которое можно отсортировать все числа в порядке возрастания.
Для набора, который я дал, вывод такой:
7
1
Есть только код класса графа:
Graph.h

#pragma once
#include <iostream>
class Graph
{
    int size;
    int** matrix;
public:
    Graph();
    Graph(int size);
    Graph(int size, int** matrix);
    Graph(const Graph& tmp);
    ~Graph();
    Graph& operator=(const Graph& tmp);
    void add_edge(int i, int j);
    void remove_edge(int i, int j);
    void add_vertex(int n);
    void remove_vertex(int n);
    bool is_edge(int i, int j);
    int get_vertex();
    int get_size();
    int** get_matrix();
    friend std::ostream& operator <<(std::ostream& out, const Graph& tmp);
};

Graph.cpp

#include "Graph.h"
 
Graph::Graph(): size(0), matrix(nullptr) {}
 
Graph::Graph(int size): size(size)
{
    int** matrix = new int*[size];
    for (size_t i = 0; i < size; ++i)
        matrix[i] = new int[size];
 
    for (size_t i = 0; i < size; ++i)
        for (size_t j = 0; j < size; ++j)
            matrix[i][j] = 0;
}
 
Graph::Graph(int size, int** matrix) : size(size)
{
 
    this->matrix = new int* [size];
    for (size_t i = 0; i < size; ++i)
        this->matrix[i] = new int[size];
 
    for (size_t i = 0; i < size; ++i)
        for (size_t j = 0; j < size; ++j)
            this->matrix[i][j] = matrix[i][j];
}
 
Graph::Graph(const Graph& tmp)
{
    size = tmp.size;
    matrix = new int* [size];
    for (size_t i = 0; i < size; ++i)
        matrix[i] = new int[size];
    
    for (size_t i = 0; i < size; ++i)
        for (size_t j = 0; j < size; j++)
            matrix[i][j] = tmp.matrix[i][j];
}
 
Graph::~Graph()
{
    for (size_t i = 0; i < size; ++i)
        delete[] matrix[i];
    delete[] matrix;
}
 
Graph& Graph::operator=(const Graph& tmp)
{
    if (this == &tmp)
        return *this;
    else
    {
        if (matrix)
        {
            for (size_t i = 0; i < size; ++i)
                delete[] matrix[i];
            delete[] matrix;
        }
            
        for (size_t i = 0; i < size; ++i)
            matrix[i] = new int[size];
 
        for (size_t i = 0; i < size; ++i)
            for (size_t j = 0; j < size; j++)
                matrix[i][j] = tmp.matrix[i][j];
        return *this;
    }
}
 
void Graph::add_edge(int i, int j)
{
    --i; --j;
    if (i < size && j < size && i > -1 && j > -1)
    {
        matrix[i][j] = 1;
        matrix[j][i] = 1;
    }
 
}
 
void Graph::remove_edge(int i, int j)
{
    if (i < size && j < size && i > -1 && j > -1)
    {
        matrix[i][j] = 0;
        matrix[j][i] = 0;
    }
}
 
void Graph::add_vertex(int n)
{
    int** tmparr = new int* [size];
    for (size_t i = 0; i < size; ++i)
        tmparr[i] = new int[size];
 
    for (size_t i = 0; i < size; ++i)
        for (size_t j = 0; j < size; ++j)
            tmparr[i][j] = matrix[i][j];
 
    for (size_t i = 0; i < size; ++i)
        delete[] matrix[i];
    delete[] matrix;
 
    size += n;
    int** matrix = new int* [size];
    for (size_t i = 0; i < size; ++i)
        matrix[i] = new int[size];
 
    for (size_t i = 0; i < size-n; ++i)
        for (size_t j = 0; j < size-n; ++j)
            matrix[i][j] = tmparr[i][j];
 
    for (size_t i = size - n; i < size; ++i)
        for (size_t j = size - n; j < size; ++j)
            matrix[i][j] = 0;
}
 
void Graph::remove_vertex(int n)
{
    int** tmparr = new int* [size];
    for (size_t i = 0; i < size; ++i)
        tmparr[i] = new int[size];
 
    for (size_t i = 0; i < size; ++i)
        for (size_t j = 0; j < size; ++j)
            tmparr[i][j] = matrix[i][j];
 
    for (size_t i = 0; i < size; ++i)
        delete[] matrix[i];
    delete[] matrix;
 
    size -= n;
    int** matrix = new int* [size];
    for (size_t i = 0; i < size; ++i)
        matrix[i] = new int[size];
 
    for (size_t i = 0; i < size; ++i)
        for (size_t j = 0; j < size; ++j)
            matrix[i][j] = tmparr[i][j];
}
 
bool Graph::is_edge(int i, int j)
{
    return matrix[i][j];
}
 
int Graph::get_size()
{
    return size;
}
 
int** Graph::get_matrix()
{
    return matrix;
}
 
std::ostream& operator<<(std::ostream& out, const Graph& tmp)
{
 
    out << "  ";
    for (size_t i = 1; i <= tmp.size; ++i)
        out << i << ' ';
    out << '\n';
    
    for (size_t i = 0; i < tmp.size; ++i)
    {
        out << i + 1 << ' ';
        for (size_t j = 0; j < tmp.size; ++j)
            out << tmp.matrix[i][j] << ' ';
        out << '\n';
    }
    return out;
}

[Moctavius]

В Сортирующей Игре изначально задана перестановка чисел от 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

[Пётр Седов]

Moctavius, тут не обязательно хранить граф в явном виде. Можно так:

#include <assert.h>
#include <string.h>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>

using namespace std;

typedef unsigned char byte_t;

const int _max_permut_len = 8;

// возвращает len! (len факториал)
int permuts_count(int len) {
  assert((1 <= len) && (len <= _max_permut_len));
  int count = 1;
  for (int i = 2; i <= len; i++) {
    count *= i;
  }
  return count;
  // возможная оптимизация: можно один раз просчитать все значения функции в массив, а потом просто брать из массива
}

int permut_index(const byte_t* elems, int len) {
  assert((1 <= len) && (len <= _max_permut_len));

  if (len == 1) {
    assert(elems[0] == 1);
    return 0;
  }

  int first_elem = elems[0];
  assert((1 <= first_elem) && (first_elem <= len));

  byte_t lesser_elems[_max_permut_len - 1];
  for (int i = 1; i < len; i++) {
    int e = elems[i];
    assert(e != first_elem);
    lesser_elems[i - 1] = (e < first_elem ? e : e - 1);
  }

  return (first_elem - 1) * permuts_count(len - 1) + permut_index(lesser_elems, len - 1);
}

struct permut_t { // permutation (перестановка)
  byte_t elems[_max_permut_len];
  int dist_from_start;
};

vector<permut_t> _permuts;
int _cur_permut_index;
byte_t _cur_permut[_max_permut_len];
int _cur_permut_pos;

void generate_permuts(const byte_t* elems, int len) {
  assert((1 <= len) && (len <= _max_permut_len));

  if (len == 1) {
    _cur_permut[_cur_permut_pos] = elems[0];
    int permut_len = _cur_permut_pos + 1;
    assert(permut_index(_cur_permut, permut_len) == _cur_permut_index);
    permut_t* p = &_permuts[_cur_permut_index];
    memcpy(p->elems, _cur_permut, permut_len);
    p->dist_from_start = -1; // нет определённого значения
    _cur_permut_index++;
    return;
  }

  for (int i = 0; i < len; i++) {
    _cur_permut[_cur_permut_pos] = elems[i];

    byte_t lesser_elems[_max_permut_len - 1];
    memcpy(lesser_elems, elems, i); // копируем элементы до i-го
    memcpy(lesser_elems + i, elems + (i + 1), len - (i + 1)); // копируем элементы после i-го
    _cur_permut_pos++;
    generate_permuts(lesser_elems, len - 1);
    _cur_permut_pos--;
  }
}

// permut_len -- n
// reverse_len -- k
int sort_dist(int permut_len, int reverse_len, const byte_t* start_permut_elems) {
  assert((2 <= reverse_len) && (reverse_len <= permut_len) && (permut_len <= _max_permut_len));

  int count = permuts_count(permut_len);
  _permuts.resize(count);
  _cur_permut_index = 0;
  _cur_permut_pos = 0;
  byte_t elems[_max_permut_len];
  for (int i = 0; i < permut_len; i++) { // в новых компиляторах можно использовать функцию std::iota
    elems[i] = 1 + i;
  }
  generate_permuts(elems, permut_len);
  assert(_cur_permut_index == count);

  // на первом месте стоит перестановка, у которой элементы идут по возрастанию
  permut_t* target_permut = &_permuts[0];
  assert(memcmp(target_permut->elems, elems, permut_len) == 0);

  int start_permut_index = permut_index(start_permut_elems, permut_len);
  permut_t* start_permut = &_permuts[start_permut_index];

  // поиск в ширину, чтобы найти путь от start_permut до target_permut
  if (start_permut == target_permut) {return 0;}
  queue<permut_t*, list<permut_t*> > boundary_permuts;
  start_permut->dist_from_start = 0;
  boundary_permuts.push(start_permut);
  do {
    permut_t* permut = boundary_permuts.front();
    boundary_permuts.pop();
    // перебираем все смежные (adjacent) перестановки
    for (int reverse_pos = 0; reverse_pos <= permut_len - reverse_len; reverse_pos++) {
      memcpy(elems, permut->elems, permut_len);
      reverse(elems + reverse_pos, elems + (reverse_pos + reverse_len));
      int adjacent_permut_index = permut_index(elems, permut_len);
      permut_t* adjacent_permut = &_permuts[adjacent_permut_index];
      if (adjacent_permut->dist_from_start == -1) { // если нет определённого значения
        adjacent_permut->dist_from_start = permut->dist_from_start + 1;
        if (adjacent_permut == target_permut) {return adjacent_permut->dist_from_start;}
        boundary_permuts.push(adjacent_permut);
      }
    }
  } while (!boundary_permuts.empty());
  return -1;
}

int main() {
  const byte_t e1[3] = {1, 2, 3};
  assert(sort_dist(3, 3, e1) == 0);

  const byte_t e2[3] = {3, 2, 1};
  assert(sort_dist(3, 3, e2) == 1);

  const byte_t e3[8] = {7, 2, 1, 6, 8, 4, 3, 5};
  assert(sort_dist(8, 4, e3) == 7);

  const byte_t e4[5] = {3, 2, 4, 1, 5};
  assert(sort_dist(5, 4, e4) == -1);

  return 0;
}

Вместо функции generate_permuts может быть имеет смысл использовать функцию std::next_permutation. Но не факт, что она тут подойдёт. Не изучал этот вопрос.

Сообщение от Moctavius

Пример входа
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

Сами сможете написать parsing такого файла? Через какой-нибудь iostreams например.