Обход 2D массива по спирали с использованием рекурсии

Question

Я готовлюсь к интервью и застрял в этом вопросе довольно давно. Может кто-нибудь, пожалуйста, помогите мне с кодом. Если не завершено, то может быть фрагмент этого? Пожалуйста..

Answer 1

Python 2, печатает вложенный 2D-список по часовой стрелке, от верхнего левого угла до центра:

>>> def clockwise(r):
...     return list(r[0]) + clockwise(list(reversed(zip(*r[1:])))) if r else []
... 
>>> a = [ 
...   [ 1,  2,  3], 
...   [ 5,  6,  7], 
...   [ 9, 10, 11]]
>>> clockwise(a)
[1, 2, 3, 7, 11, 10, 9, 5, 6]
>>> a = [ 
...   [ 1,  2,  3,  4], 
...   [ 5,  6,  7,  8], 
...   [ 9, 10, 11, 12],
...   [13, 14, 15, 16]]
>>> clockwise(a)
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

Так что здесь происходит? Аргумент к clockwise это двумерный массив r, Мы хотим напечатать его содержимое слева направо, по часовой стрелке. Так что, если двумерный массив не пустой, то мы можем напечатать его первый элемент, который является верхней строкой. Далее мы хотим напечатать последние элементы оставшихся строк (числа справа). Мы не хотим повторяться. Так что мы делаем, чтобы преобразовать оставшиеся строки таким образом, чтобы следующие числа были напечатаны в верхнем ряду. Мы делаем это путем транспонирования оставшихся строк (чтобы они стали столбцами) и затем обращаем их вспять.

Возможно, алгоритм станет понятнее, если я напишу его на Хаскеле:

import Data.List

clockwise :: [[a]] -> [a] 
clockwise (x:xs) = x ++ (clockwise $ reverse $ transpose $ xs) 
clockwise _      = []

Answer 2

Код ниже по существу делает то, что он разделяет массив на слои. Таким образом, все внешние элементы, то есть первая строка, последний столбец, последняя строка и первый столбец, будут составлять первый слой. Второй слой будет состоять из всех элементов, находящихся непосредственно внутри первого слоя, и так далее.

После экспериментов с несколькими комбинациями номеров строк и столбцов я пришел к выводу, что количество слоев определяется половиной количества строк или половиной количества столбцов, в зависимости от того, что меньше (округление до десятичных знаков).

Вызовshell()на каждом слое эффективно позволяет вам перемещаться и располагаться в спиральном порядке.

      import java.util.Scanner;

//program to input elements in spiral order 
public class spiral{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("enter number of rows");
        int m = sc.nextInt();
        System.out.println("enter number of columns");
        int n = sc.nextInt();
        int arr[][] = new int[m][n];
        /*
         * recursive approach is used here
         * shell() takes input for only the outer layer of the array
         * mid stores the number of layers, which is half of the number of rows or
         * columns whichever is lesser
         * calling shell() for each layer of the array effectively returns an array in
         * spiral order
         */

        int mid = arr.length > arr[0].length ? (int) Math.ceil(arr[0].length / 2) : (int) Math.ceil(arr.length / 2);

        for (int i = 0; i < mid; i++) {
            shell(arr, i, arr[0].length - i - 1, i, arr.length - i - 1);
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }

    // iterate through first row, last column, last row and first column in order
    public static void shell(int arr[][], int col_start, int col_end, int row_start, int row_end) {
        //Here I am taking input for the array. Whatever is inside each of 
        //these loops can be manipulated. 
        for (int i = col_start; i < col_end; i++) {
            arr[row_start][i] = new Scanner(System.in).nextInt();
        }
        for (int i = row_start; i < row_end; i++) {
            arr[i][col_end] = new Scanner(System.in).nextInt();
        }
        for (int i = col_end; i > col_start; i--) {
            arr[row_end][i] = new Scanner(System.in).nextInt();
        }
        for (int i = row_end; i > row_start; i--) {
            arr[i][col_start] = new Scanner(System.in).nextInt();
        }

    }
}