将二维矩阵转换为螺旋顺序 [英] To convert a two dimensional matrix to spiral order

问题描述

你好CPs，

已经很久了。我坚持一个想法，我需要你的意见或解决方案。所以我走了。



让我们考虑一个4x4矩阵

 | 1 2 3 4 | 
 | 5 6 7 8 | 
 | 9 10 11 12 | 
 | 13 14 15 16 | 

按螺旋顺序，它将被重写为1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10.



那么我的条件会怎样？我为4x4矩阵编写了一个程序，但每次矩阵增大时都必须增加IF条件。我的输入并不总是一个方阵。那么如何使这个动态？

解决方案

对不起，我之前没有回复你。想知道这是什么来的。



这是我设计的：

  public   static   partial   class 数组
 {
  public   static  System.Collections.Generic.IEnumerable< T> 
 Spiral< T> 
（
 此 T [，] Matrix 
）
 {
  int  top = Matrix.GetLowerBound（ 0 ）
，bot = Matrix.GetUpperBound（ 0 ）
，lft = Matrix.GetLowerBound（ 1 ）
，rgt = Matrix.GetUpperBound（ 1 ）; 
 
  while （top <  = bot）
 {
  for （ int  i = lft; i < ;  = rgt; i ++） yield   return （Matrix [top，i]）; 
 top ++; 
 
  for （ int  i = top; i <  = bot; i ++） yield   return （Matrix [i， rgt]）; 
 rgt--; 
 
  for （ int  i = rgt; i >  = lft; i--） yield   return （Matrix [机器人，我]）; 
 bot--; 
 
  for （ int  i = bot; i >  = top; i--） yield   return （Matrix [我，lft]）; 
 lft ++; 
} 
 
  yield   break ; 
} 
} 

这样做怎么样：你的螺旋只是嵌套的矩形。外部矩形从（0,0）开始，下一个内部开始于（1,1），依此类推，直到达到（宽度+ 1）/ 2; （注意+1以满足奇数宽度）。



所以我会为它创建一个外循环，比如

  int  i; 
  int  cntRects =（width +  1 ）/  2 ; 
 
  for （i =  0 ; i< cntRects; ++ i ）
 {
 ... 
 

在外部循环中你做了四个内循环矩形的四边，即顶部，右边，底部，左边。您可以从i，宽度和高度轻松构建索引。在这里，我将为您做第一个：

  int  x，y; 
 
  //   top side  
 y = i; 
  for （x = i; x< width  -  i; ++ i）
 AddPoint（x，y）; 
 
 ... 
 

您可以使用<$ c $创建一个簿记矩阵，比如说已访问 c>如果访问了原始矩阵中的相同项目，则访问[j] [k] = 1 。现在假设您正在进行正 x -axis，然后如果访问[y] [x + 1] == 1 （或 x == N-1 ，即你在边界上）然后你必须改变方向（在这个例子中，你必须下去）。

Hi CPs,
Its been a long time. And I'm stuck at an idea and I need your opinions or solutions to it. So here I go.

Lets consider a 4x4 matrix

|1  2  3  4  |
|5  6  7  8  |
|9  10 11 12 |
|13 14 15 16 |

In a spiral order it will be re-written as 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10.

So how would my conditions go? I wrote a program for a 4x4 matrix but the IF-conditions has to be increased each time the matrix grows in size. And my input won't always be a square matrix. So how to make this dynamic?

解决方案

Sorry I didn't get back to you earlier. Wondering what came of this.

Here's what I devised:

public static partial class Array
{
  public static System.Collections.Generic.IEnumerable<T>
  Spiral<T>
  (
    this T[,] Matrix
  )
  {
    int top = Matrix.GetLowerBound ( 0 )
      , bot = Matrix.GetUpperBound ( 0 )
      , lft = Matrix.GetLowerBound ( 1 )
      , rgt = Matrix.GetUpperBound ( 1 ) ;

    while ( top <= bot )
    {
      for ( int i = lft ; i <= rgt ; i++ ) yield return ( Matrix [ top ,   i ] ) ;
      top++ ;

      for ( int i = top ; i <= bot ; i++ ) yield return ( Matrix [   i , rgt ] ) ;
      rgt-- ;

      for ( int i = rgt ; i >= lft ; i-- ) yield return ( Matrix [ bot ,   i ] ) ;
      bot-- ;

      for ( int i = bot ; i >= top ; i-- ) yield return ( Matrix [   i , lft ] ) ;
      lft++ ;
    }

    yield break ;
  }
}

How about doing it this way: Your spiral is nothing but nested rectangles. The outer rectangle starts at (0,0), the next inner one at (1,1), and so forth until you reach (width+1)/2; (note the +1 to cater for odd widths).

So I would create an outer loop for that, say

int i;
int cntRects = (width + 1) / 2;

for (i = 0; i < cntRects; ++i)
{
    ...

Inside that outer loop you do four inner loops for the four sides of the rectangle, i.e. top, right, bottom, left. You can construct the indices easily from i, width and height. Here I am going to do the first one for you:

int x, y;

// top side
y = i;
for (x = i; x < width - i; ++i)
    AddPoint (x, y);

...

You could create a bookkeeping matrix, say 'visited', with visited[j][k]=1 if the same item in the original matrix has been visited. Now suppose you are proceeding on the positive x-axis, then if visited[y][x+1] == 1 (or x == N-1, that is you are on a boundary) then you have to change direction (in this example, you have to go down).

这篇关于将二维矩阵转换为螺旋顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！