Рубрики

Распечатать заданную матрицу в виде спирали, используя метод отслеживания направления

Учитывая двумерный матричный мат [] [] , задача состоит в том, чтобы напечатать его в виде спирали.

Примеры:

Input: mat[][] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Input: mat[][] = {
{1, 2, 3, 4, 5, 6},
{7, 8, 9, 10, 11, 12},
{13, 14, 15, 16, 17, 18}}
Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11

Подход: эту проблему легко решить, используя метод направления. Поскольку мы начинаем с восточного направления, то всегда поворачиваем направо, когда следующий индекс либо недействителен (вне матрицы), либо посещен ранее. Далее следуют следующие направления: Восток -> Юг -> Запад -> Север ->… начиная с mat [0] [0] и заканчивая, наконец, после прохождения всех элементов матрицы.

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

#define R 5
#define C 5

  

enum direction { east,

                 west,

                 north,

                 south };

  
// Функция установки нового направления на поворот
// прямо с текущего направления

void turnright(enum direction& c_direction)

{

    switch (c_direction) {

    case east:

        c_direction = south;

        break;

    case west:

        c_direction = north;

        break;

    case north:

        c_direction = east;

        break;

    case south:

        c_direction = west;

        break;

    }

}

  
// Функция для возврата следующей возможной ячейки
// указатели с текущим направлением

pair<int, int> next(int i, int j,

                    const enum direction& c_direction)

{

    switch (c_direction) {

    case east:

        j++;

        break;

    case west:

        j--;

        break;

    case north:

        i--;

        break;

    case south:

        i++;

        break;

    }

    return pair<int, int>(i, j);

}

  
// Функция, которая возвращает true
// если arr [i] [j] является допустимым индексом

bool isvalid(const int& i, const int& j)

{

    if (i < R && i >= 0 && j >= 0 && j < C)

        return true;

    return false;

}

  
// Функция, которая возвращает true, если arr [i] [j]
// уже посетили

bool alreadyVisited(int& i, int& j, int& mini, int& minj,

                    int& maxi, int& maxj)

{

  

    // Если внутри текущих границ, то

    // это не было посещено ранее

    if (i >= mini && i <= maxi && j >= minj && j <= maxj)

        return false;

    return true;

}

  
// Функция обновления ограничений матрицы

void ConstraintWalls(int& mini, int& minj, int& maxi,

                     int& maxj, direction c_direction)

{

  

    // Обновляем ограничения в соответствии

    // в направлении

    switch (c_direction) {

    case east:

        mini++;

        break;

    case west:

        maxi--;

        break;

    case north:

        minj++;

        break;

    case south:

        maxj--;

        break;

    }

}

  
// Функция для печати заданной матрицы в виде спирали

void printspiral(int arr[R][C])

{

  

    // Хранить счетчик всех индексов

    int count = 0;

  

    // Начальное направление - восток

    enum direction current_direction = east;

  

    // Граничные ограничения в матрице

    int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1;

    int i = 0, j = 0;

  

    // Пока остаются элементы

    while (count < (R * C)) {

  

        // Распечатать текущий элемент

        // и увеличиваем количество

        cout << arr[i][j] << " ";

        count++;

  

        // Следующая возможная ячейка, если направление остается прежним

        pair<int, int> p = next(i, j, current_direction);

  

        // Если текущая ячейка уже посещена или недействительна

        if (!isvalid(p.first, p.second)

            || alreadyVisited(p.first, p.second, mini, minj, maxi, maxj)) {

  

            // Если не посещали ранее, то меняем только ограничение

            if (!alreadyVisited(i, j, mini, minj, maxi, maxj))

                ConstraintWalls(mini, minj, maxi, maxj, current_direction);

  

            // Изменить направление

            turnright(current_direction);

  

            // Следующие указатели с новым направлением

            p = next(i, j, current_direction);

        }

  

        // Следующая строка и следующий столбец

        i = p.first;

        j = p.second;

    }

}

  
// Код драйвера

int main()

{

    int arr[R][C];

  

    // Заполнить матрицу

    int counter = 1;

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

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

            arr[i][j] = counter++;

  

    // Распечатать спиральную форму

    printspiral(arr);

  

    return 0;

}

Выход:

1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13

Сложность времени: O (R * C)
Космическая сложность: O (1)

Рекомендуемые посты:

Распечатать заданную матрицу в виде спирали, используя метод отслеживания направления

0.00 (0%) 0 votes