Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

Входные данные

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

Выходные данные

Искомое количество шагов.

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
5	3 2 6 12	2

Код 1

#include <iostream>
using namespace std;

int main()
{
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    //создание динамического массива
    int*** arr;
    arr = new int**[vertSize];
    int count = 1;
    int z = 2;
    int apos[3];
    int bpos[3];
    for (int i = 0; i < vertSize; i++)
    {
        arr[i] = new int*[horSize];
        for (int j = 0; j < horSize; j++)
        {
            arr[i][j] = new int[z];
            for (int k = 0; k < 2; k++)
            {
                arr[i][j][k] = count;
                count++;
                // определяем позицию наших элементов в массиве
                if (arr[i][j][k] == firstNumber)
                {
                    apos[0] = i;
                    apos[1] = j;
                    apos[2] = k;
                }
                if (arr[i][j][k] == lastNumber)
                {
                    bpos[0] = i;
                    bpos[1] = j;
                    bpos[2] = k;
                }
            }
        }
    }
    int hor;
    int vert;
    // направление движения по вертикали
    vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);
    // направление движения по горизонтали
    hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);
    int stepCount = 0;
    int curCell[3];
    for (int i = 0; i < 3; i++)
        curCell[i] = apos[i];

    bool dir;
    if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)
        dir = false;
    else
        dir = true;
    while (1)
    {
        if (dir && vert != 0)
        {
            if (vert == -1)
            {
                if (curCell[2] == 0)
                    curCell[0]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[0]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        else if (!dir && hor != 0)
        {
            if (hor == -1)
            {
                if (curCell[2] == 0)
                    curCell[1]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[1]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        dir = !dir;

        if (curCell[0] == bpos[0])
            vert = 0;
        if (curCell[1] == bpos[1])
            hor = 0;

        if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])
        {
            curCell[2] = !((bool)curCell[2]);
            stepCount++;
        }

        bool end;
        for (int i = 0; i < 3; i++)
        {
            if (curCell[i] != bpos[i])
            {
                end = false;
                break;
            }
            end = true;
        }
        if (end)
            break;
    }
    cout << stepCount << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <iostream>

using namespace std;

int main()

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

//создание динамического массива

int*** arr;

arr = new int**[vertSize];

int count = 1;

int z = 2;

int apos[3];

int bpos[3];

for (int i = 0; i < vertSize; i++)

{

arr[i] = new int*[horSize];

for (int j = 0; j < horSize; j++)

{

arr[i][j] = new int[z];

for (int k = 0; k < 2; k++)

{

arr[i][j][k] = count;

count++;

// определяем позицию наших элементов в массиве

if (arr[i][j][k] == firstNumber)

{

apos[0] = i;

apos[1] = j;

apos[2] = k;

}

if (arr[i][j][k] == lastNumber)

{

bpos[0] = i;

bpos[1] = j;

bpos[2] = k;

}

int hor;

int vert;

// направление движения по вертикали

vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);

// направление движения по горизонтали

hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);

int stepCount = 0;

int curCell[3];

for (int i = 0; i < 3; i++)

curCell[i] = apos[i];

bool dir;

if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)

dir = false;

else

dir = true;

while (1)

{

if (dir && vert != 0)

{

if (vert == -1)

{

if (curCell[2] == 0)

curCell[0]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[0]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else if (!dir && hor != 0)

{

if (hor == -1)

{

if (curCell[2] == 0)

curCell[1]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[1]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

dir = !dir;

if (curCell[0] == bpos[0])

vert = 0;

if (curCell[1] == bpos[1])

hor = 0;

if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])

{

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

bool end;

for (int i = 0; i < 3; i++)

{

if (curCell[i] != bpos[i])

{

end = false;

break;

}

end = true;

}

if (end)

break;

}

cout << stepCount << endl;

return 0;

}

Код 2

#include <iostream>
using namespace std;
int main() {
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    if (firstNumber > lastNumber){
        swap(firstNumber, lastNumber);  
    } 
    //вычисление координат
    int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    int Search[2 * horSize];
    Search[firstNumberx - 1] = 0;
    int step = 1;
    for (int i = firstNumberx - 2; i >= 0; i--){
        Search[i] = step++;
        
    }
    step = 1;
    for (int i = firstNumberx; i < 2 * horSize; i++){
        Search[i] = step++;
    }
    //сравнение по у
    for (int j = firstNumbery; j < lastNumbery; j++) {
        for (int i = 1; i < 2 * horSize; i += 2) {
            Search[i - 1] = Search[i] + 1;
            Search[i] += 2;
            //определние значения на предпоследнем элементе
            if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                Search[i - 2] = Search[i];
            }
        }
    }
    cout << Search[lastNumberx - 1] << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

if (firstNumber > lastNumber){

swap(firstNumber, lastNumber);

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int Search[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

for (int i = firstNumberx; i < 2 * horSize; i++){

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

for (int i = 1; i < 2 * horSize; i += 2) {

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определние значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

cout << Search[lastNumberx - 1] << endl;

return 0;

}

Решение задачи

Способ 1

Каждый элемент имеет три параметра:

Положение в строке
Положение в столбце
Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

Оба элемента расположены в одной строке строке
Оба элемента расположены в одном столбце
Оба элемента расположены на одной диагонали
Произвольное расположение

Для удобства мы завели счетчик шагов.
Рассмотрим случай когда первый элемент меньше, чем последний, допустим, что

firstNumber = 7;
lastNumber = 14;

1 2	firstNumber = 7; lastNumber = 14;

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

(bool)curCell[2]

1	(bool)curCell[2]

Для более оптимальной работы были использованы тернарные операции. Они скрывают под собой условие, выполнение которого состоит из одной строки кода.

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

int V[2 * horSize];

1	int V[2 * horSize];

массив, переменные в котором будет иметь тип [latex] int [/latex], а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex] int [/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции