Алгоритм спиральной матрицы

Question

У меня возникли проблемы с учетом нечетных входных событий в следующей задаче: если задана матрица из m x n элементов (m строк, n столбцов), верните все элементы матрицы в спиральном порядке.

For example, 
Given the following matrix: 

[ 
[ 1, 2, 3 ], 
[ 4, 5, 6 ], 
[ 7, 8, 9 ] 
] 
You should return [1,2,3,6,9,8,7,4,5]. 

Мой код работает на всех крупных тестовых случаев, но не выполняется для таких вещей, как

[[6,9,7]] 

, и я не знаю, как построить мой код для обработки этих входов. У кого-нибудь есть идеи?

def spiral_order(matrix) 
    return nil if matrix.nil? 
    return [] if matrix.empty? 
    m = matrix.length - 1 
    n = matrix.first.length - 1 
    start_col = start_row = 0 
    end_col = n 
    end_row = m 
    visited = [] 
    iter = 0 
    until start_row > end_row && start_col > end_col 
     until iter > end_col 
      visited << matrix[start_row][iter] 
      iter+=1 
     end 
     start_row += 1 
     iter = start_row 

     until iter > end_row 
      visited << matrix[iter][end_col] 
      iter += 1 
     end 
     end_col -= 1 
     iter = end_col 

     until iter < start_col 
      visited << matrix[end_row][iter] 
      iter-=1 
     end 
     end_row -= 1 
     iter = end_row 

     until iter < start_row 
      visited << matrix[iter][start_col] 
      iter -= 1 
     end 
     start_col += 1 
     iter = start_col 
    end 

    visited 
end 

На [6,9,7] Я получаю ноль ошибку на линии 17. Я знаю, что весь цикл работает в два раза (это само по себе не должно быть так, потому что я приращения начинать лимиты и уменьшать конечные пределы), но я изо всех сил пытаюсь создать код, который работает как для обычных входов, так и для странных случаев, не бросая тонну условных выражений для обработки более необычных случаев.

Answer 1

Это можно решить, используя гораздо более простой набор кода. Стрите верхний ряд из матрицы, поверните матрицу, повторите до пустого.

def spiral_order(matrix) 
    m = matrix.dup 
    result = [] 
    until m.size < 1 
    result << m.shift 
    m = m.transpose.reverse 
    end 
    result.flatten 
end 

>> matrix = [[1,2,3],[4,5,6],[7,8,9]] 
>> spiral_order(matrix) 
=> [1, 2, 3, 6, 9, 8, 7, 4, 5] 

>> matrix = [[6,9,7]] 
>> spiral_order(matrix) 
=> [6, 9, 7] 

Если вы работаете с большими матрицами и хотите избежать множества дупликации, для немногих дополнительной сложности вы можете сделать это:

def spiral_order(matrix) 
    m = matrix.map(&:dup) 
    result = [] 
    until m.size < 1 
    result << m.shift 
    result << m.map(&:pop) 
    result << (m.pop || []).reverse 
    result << m.map(&:shift).reverse 
    end 
    result.flatten.compact 
end 

Алгоритм работает следующим образом: Line 2 глубоководных дубликаты матрица, так что оригинал, прошедший внутри, не тронут. Строка 5 удаляет верхний ряд. Строка 6 удаляется с правой колонки. Строка 7 удаляет нижний ряд и отменяет его. (|| [] гарантирует, что мы не вызываем #reverse по значению nil.) Строка 8 удаляет левый столбец и меняет его. Строки 5-8 повторяются до тех пор, пока матрица не станет пустой. В этот момент строка 10 удаляет внутренние массивы и nils и возвращает результат.