БлогNot. Закручивающаяся спираль

Закручивающаяся спираль

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

Требуется, начав с левого верхнего угла и двигаясь по часовой стрелке вправо, вывести элементы, например, для данных

 1  2  3  4
 5  6  7  8
 9 10 11 12

вывод будет в порядке

 1  2  3  4  8 12 11 10  9  5  6  7

Вот вариант с обычными итерациями:

#include <iostream> 
using namespace std;

void spiralPrint(int m, int n, int **a) {
 int i, k = 0, l = 0; // начать с элемента [k][l]
 while (k < m && l < n) {
  for (i = l; i < n; ++i) cout << a[k][i] << endl;
  k++;
  for (i = k; i < m; ++i) cout << a[i][n - 1] << endl;
  n--;
  if (k < m) {
   for (i = n - 1; i >= l; --i) cout << a[m - 1][i] << endl;
   m--;
  }
  if (l < n) {
   for (i = m - 1; i >= k; --i) cout << a[i][l] << endl;
   l++;
  }
 }
}

int main() {
 const int R = 3, C = 4; //строк и столбцов
 int** a = new int* [R];
 int k = 1;
 for (int i = 0; i < R; i++) { //формирование матрицы
  a[i] = new int[C];
  for (int j = 0; j < C; j++) a[i][j] = k++;
 }

 spiralPrint(R, C, a); //обработка

 cin.get();
 return 0;
}

Ввод здесь просто формированием матрицы матрицы по правилу, с чтением из файла или с консоли не заморачивался.

Либо, как всегда, итерации можно заменить рекурсией, вариант 2:

#include <iostream> 
using namespace std;

void spiralPrint (int **arr, int i, int j, int m, int n) {
 if (i >= m or j >= n) return; //не лезь за матрицу, там нет синей таблетки
 for (int p = i; p < n; p++) cout << arr[i][p] << endl; //строка 1 
 for (int p = i + 1; p < m; p++) cout << arr[p][n - 1] << endl; //последний столбец
 if ((m - 1) != i)for (int p = n - 2; p >= j; p--) cout << arr[m - 1][p] << endl;
  //если последняя строка не подобна первой...
 if ((n - 1) != j) for (int p = m - 2; p > i; p--) cout << arr[p][j] << endl;
  //и столбец первый не станет последним...
 spiralPrint (arr, i + 1, j + 1, m - 1, n - 1); //то вызови себя, и постигни истину
}

int main() {
 const int R = 3, C = 4; //строк и столбцов
 int** a = new int* [R];
 int k = 1;
 for (int i = 0; i < R; i++) { //формирование матрицы
  a[i] = new int[C];
  for (int j = 0; j < C; j++) a[i][j] = k++;
 }

 spiralPrint (a, 0, 0, R, C);
 cin.get();
 return 0;
}

Это приятней, но потенциально памяти съест больше. Возможно, это даже O(n*m) по времени. Запускал в консоли Visual Studio 2019. А как сделать экономичней? Ясно, что искать надо в направлении жадных алгоритмов, но они потому и жадные, что решений в общем виде не гарантируют.

16.06.2020, 15:51 [1304 просмотра]


теги: c++ памятка числа алгоритм

К этой статье пока нет комментариев, Ваш будет первым