Распечатайте заданную матрицу в форме спирали, используя метод отслеживания направления
Учитывая двумерный матричный мат [] [] , задача состоит в том, чтобы распечатать его в виде спирали.
Примеры:
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 10Input: 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
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: Эту проблему легко решить, используя метод направления. Поскольку мы начинаем с восточного направления, то всегда поворачиваем направо, если следующий индекс либо недействителен (вне матрицы), либо посещен ранее. Следующие направления будут: Восток -> Юг -> Запад -> Север ->… начиная с mat [0] [0] и заканчивая, наконец, когда все элементы матрицы пройдены.
Below is the implementation of the above approach:
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define R 5#define C 5 enum direction { east, west, north, south }; // Function to set the new direction on turning// right from the current directionvoid 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; }} // Function to return the next possible cell// indexes with current directionpair<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);} // Function that returns true// if arr[i][j] is a valid indexbool isvalid(const int& i, const int& j){ if (i < R && i >= 0 && j >= 0 && j < C) return true; return false;} // Function that returns true if arr[i][j]// has already been visitedbool alreadyVisited(int& i, int& j, int& mini, int& minj, int& maxi, int& maxj){ // If inside the current bounds then // it has not been visited earlier if (i >= mini && i <= maxi && j >= minj && j <= maxj) return false; return true;} // Function to update the constraints of the matrixvoid ConstraintWalls(int& mini, int& minj, int& maxi, int& maxj, direction c_direction){ // Update the constraints according // to the direction switch (c_direction) { case east: mini++; break; case west: maxi--; break; case north: minj++; break; case south: maxj--; break; }} // Function to print the given matrix in the spiral formvoid printspiral(int arr[R][C]){ // To store the count of all the indexes int count = 0; // Starting direction is East enum direction current_direction = east; // Boundary constraints in the matrix int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1; int i = 0, j = 0; // While there are elements remaining while (count < (R * C)) { // Print the current element // and increment the count cout << arr[i][j] << " "; count++; // Next possible cell if direction remains the same pair<int, int> p = next(i, j, current_direction); // If current cell is already visited or is invalid if (!isvalid(p.first, p.second) || alreadyVisited(p.first, p.second, mini, minj, maxi, maxj)) { // If not visited earlier then only change the constraint if (!alreadyVisited(i, j, mini, minj, maxi, maxj)) ConstraintWalls(mini, minj, maxi, maxj, current_direction); // Change the direction turnright(current_direction); // Next indexes with new direction p = next(i, j, current_direction); } // Next row and next column i = p.first; j = p.second; }} // Driver codeint main(){ int arr[R][C]; // Fill the matrix int counter = 1; for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) arr[i][j] = counter++; // Print the spiral form 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)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.