スパイラル行列アルゴリズム

Question

以下の問題で、奇数入力の場合を説明するのに問題があります。m×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]] 

のようなもののために失敗し、私はこれらの入力を処理するために私のコードを作成するかどうかはわかりません。誰でもアイデアはありますか？ [6,9,7]私は私が増加していますので（これ自体がケースではありません、私はループ全体が二回実行されます知っているライン17にはnilエラーを取得していますオン

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 

エンドリミットを減らしたり、エンドリミットを減らしたりします）、私は通常の入力と奇妙なケースの両方で動作するコードを作成するのに苦労しています。

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] 

あなたはこれを行うことができます追加の複雑さのビットのために、大規模な行列での作業や、複数の重複を避けたいしている場合：ライン2ディープ重複：アルゴリズムは、このように動作します

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 

渡されたオリジナルが元に戻されるような行列。 5行目は一番上の行を取り除きます。 6行目は右の列を取り除きます。 7行目は一番下の行を取り除き、それを元に戻します。 （|| []は、#reverseをゼロ値にしないことを確実にしています。）8行目は、左側の列を取り除き、それを元に戻します。行5-8は、行列が空になるまで繰り返されます。その時点で、10行目は内部配列とnilsを削除し、結果を返します。