求螺旋矩阵的最佳算法

Question

手里有几个螺旋算法的代码，贴过来你看下吧，不知帮的上不
-----------------------
public class HelicalVector { 
   private int x;
   private int y;
   private int width;
   private int height;
   private String[][] value = null;    public HelicalVector(int width, int height) {
       this.width = width;
       this.height = height;
       value = new String[height][width];
   }    public String getVlaue(int x, int y) {
       StringBuffer sb = new StringBuffer(6);
       for (int i = 0, n = 6 - value[x][y].length(); i < n; i++) {
           sb.append(" ");
       }
       sb.append(value[x][y]);
       return sb.toString();
   }    public void setValue(String val) {
       value[x][y] = val;
   }    public void buildVector() {
       int direct = 0; // 以4为基数
       for (int val = 1; val <= width*height; val++) {
           setValue(String.valueOf(val));
           direct %= 4;
           switch (direct) {
               case 0:
                   if (y == width-1 || value[x][y+1] != null) {
                       direct++; //换方向
                       x++;
                   } else
                       y++;
                   break;
               case 1:
                   if (x == height-1 || value[x+1][y] != null) {
                       direct++; //换方向
                       y--;
                   } else
                       x++;
                   break;
               case 2:
                   if (y == 0 || value[x][y-1] != null) {
                       direct++; //换方向
                       x--;
                   } else
                       y--;
                   break;
               case 3:
                   if (x == 0 || value[x-1][y] != null) {
                       direct++; //换方向
                       y++;
                   } else
                       x--;
                   break;
           }
       }
   }    public void printVector() {
       for (int i = 0; i < height; i++) {
           for (int j = 0; j < width; j++) {
               System.out.print(getVlaue(i, j));
           }
           System.out.println();
       }
   }    public static void main(String[] args) {
       HelicalVector vector = new HelicalVector(7, 8);
       vector.buildVector();
       vector.printVector();
   } } 
--------------------------------------------

Answer 1

记起了，好象是在www.chinajavaworld.net里看到过的，那里的精华区的，不过最近打不开
------------------------------------------------
/*
* Copyright (c) 2003 [email protected]
* Nov. 19, 2003 for ChinaJavaWorld.net
* Permission is hereby granted, free of charge, to any one for any purpose.
*/
public interface CircleMatrix
{
  public int getHeight();
  public int getWidth();
  public int get(int x, int y);
} 
/*
* Copyright (c) 2003 [email protected]
* Nov. 19, 2003 for ChinaJavaWorld.net
* Permission is hereby granted, free of charge, to any one for any purpose.
*/
public class CircleMatrixTester
{
  static public void main(String[] args)
  {
      int h = Integer.parseInt(args[0]);
      int w = Integer.parseInt(args[1]);
      
      CircleMatrix cmOne = new CircleMatrixSmartestImpl(h, w);
      printMatrix("CircleMatrixSmartestImpl", cmOne);
      
      CircleMatrix cmTwo = new CircleMatrixShortestImpl(h, w);
      printMatrix("CircleMatrixShortestImpl", cmTwo);
  }
  
  static public void printMatrix(String title, CircleMatrix matrix)
  {
      System.out.println();
      System.out.println(title);
      
      for(int row = 0, rowSize = matrix.getHeight(); row < rowSize; row++)
      {
          for(int col = 0, colSize = matrix.getWidth(); col < colSize; col++)
          {
              int n = matrix.get(col, row);
              
              String strN;
              if(n < 10)
                  strN = "  " + n;
              else if (n < 100)
                  strN = " " + n;
              else
                  strN = String.valueOf(n);
              
              System.out.print(strN);
              System.out.print(' ');
          }
          System.out.println();
      }
  }
} /*
* Copyright (c) 2003 [email protected]
* Nov. 19, 2003 for ChinaJavaWorld.net
* Permission is hereby granted, free of charge, to any one for any purpose.
*/
public class CircleMatrixSmartestImpl
implements CircleMatrix
{
   private int     height;
   private int     width;
   private int[]   circleSum;
   
   public CircleMatrixSmartestImpl(int height, int width)
   {
       if(height <= 0 || width <= 0)
           throw new IllegalArgumentException("negative height and/or width: " + height + ", " + width);
       
       this.height = height;
       this.width  = width;
       
       buildCircleSum(width, height);
   }
   
   public int getHeight()
   {
       return height;
   }
   
   public int getWidth()
   {
       return width;
   }
   
   public int get(int x, int y)
   {
       if(x < 0 || x >= width || y < 0 || y >= height)
           return -1;
       
       int startN = 1;
       int startX = 0, endX = width - 1;
       int startY = 0, endY = height - 1;
       
       int c = Math.min(Math.min(Math.min(y - startY, endY - y), x - startX), endX - x);
       if(c > 0)
       {
           startN += circleSum[c];
           startX += c;
           endX   -= c;
           startY += c;
           endY   -= c;
       }
       
       int n = startN;
       if(y == startY)
           return n + x - startX;
       
       n += endX - startX;
       if(x == endX)
           return n + y - startY;
       
       n += endY - startY;
       if(y == endY)
           return n + endX - x;
       
       n += endX - startX;
       if(x == startX)
           return n + endY - y;
       
       return -2;   // never happen
   }
   
   private void buildCircleSum(int w, int h)
   {
       int size = (Math.min(h, w) + 1) / 2;
       circleSum = new int[size];
       if(size > 1)
       {
           circleSum[0] = 0;
           for(int k = 1; k < size; k++, h -= 2, w -= 2)
               circleSum[k] = circleSum[k - 1] + h + h + w + w - 4;
       }
   }
} /*
* Copyright (c) 2003 [email protected]
* Nov. 19, 2003 for ChinaJavaWorld.net
* Permission is hereby granted, free of charge, to any one for any purpose.
*/
public class CircleMatrixShortestImpl
implements CircleMatrix
{
   static private final int[][]  incParams  = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
   static private final int[][]  sizeParams = new int[][]{{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
   
   private int[][]  matrix;
   
   public CircleMatrixShortestImpl(int height, int width)
   {
       if(height <= 0 || width <= 0)
           throw new IllegalArgumentException("negative height and/or width: " + height + ", " + width);
       
       buildMatrix(height, width);
   }
   
   private void buildMatrix(int h, int w)
   {
       matrix = new int[h][w];
       
       int[][]  points = new int[][]{{0, 0}, {w - 1, 0}, {w - 1, h - 1}, {0, h - 1}};
       int index = 0, index2 = 1, number = 0, totalNumber = h * w;
       
       while(number < totalNumber)
       {
           for(int x = points[index][0], y = points[index][1], incX = incParams[index][1], incY = incParams[index][0],
           endX = points[index2][0] + incX, endY = points[index2][1] + incY
           ; x != endX || y != endY; x += incX, y += incY)
           {
              matrix[y][x] = ++number;
           }
           
           points[index][0]  += sizeParams[index][0];
           points[index2][0] += sizeParams[index][0];
           points[index][1]  += sizeParams[index][1];
           points[index2][1] += sizeParams[index][1];
           
           index = index2;
           index2 = (index + 1) & 3;
       }
   }
   
   public int getHeight()
   {
       return matrix.length;
   }
   
   public int getWidth()
   {
       return matrix[0].length;
   }
   
   public int get(int x, int y)
   {
       if(x < 0 || x >= getWidth() || y < 0 || y >= getHeight())
           return -1;
       
       return matrix[y][x];
   }
}-------------------------------------------------------------

Answer 2

/*
* 基本思路：采用数学方法直接计算出矩阵元素P(x,y)的值.
* 将整个矩阵看成由外道内的矩形圈组成,矩阵中任意一点P(x,y)的值=
* 位于外圈的所有点数+位于本圈上所有点数+1 
*/
public class Martrix
{
   private int H;
   private int L;    public static void main(String argv[])
   {
       Martrix m1=new Martrix(6,6);
       m1.print();
   }
   
   public Martrix()
   {
       this.H=3;
       this.L=3;
   }
   public Martrix(int x,int y)
   {
       this.H=x;
       this.L=y;
   }    //计算处于点p(x,y)前面的所有点数
   public int getDotCount(int x,int y)
   {
       return getDotCount1(H,L,x,y) + getDotCount2(H,L,x,y) + 1;
   }    //计算点P(x,y)外围矩形圈数
   public static int getN(int H,int L,int x,int y)
   {
       return Math.min(Math.min(x,y),Math.min((H-x),(L-y)));
   }    //计算点P(x,y)外围矩形圈上的点数 (等差数列 )
   public static int getDotCount1(int H,int L,int x,int y)
   {
       int N=getN(H,L,x,y);
       int S1=2*(H+L);
       int S2=2*(H+L)-8*N + 8;
       return (S1+S2)/2 * N;
   }    //计算与点P(x,y)处于同一个矩形圈上，且在点P前面的所有点数 (分段函数)
   public static int getDotCount2(int H,int L,int x,int y)
   {
       int N=getN(H,L,x,y);
       int x1=x-N;
       int y1=y-N;
       int H1=H-2*N;
       int L1=L-2*N;
       int count; 
       if(L1==0) //特列：H >=L ,L为奇数,y=(L-1)/2 实例(H=6,L=5,x=3,y=3)
          return x1 ;        if(H1==0) //特列: H < L ,H为奇数,x=(H-1)/2 实例(H=5,L=6,x=3,y=3)
          return y1;
       
       if(y1==0) //一般情况: 
       {
           count=x1;
       }
       else if(x1==H1) //一般情况: 
       {
           count=H1 + y1;
       }
       else if(y1==L1) //一般情况: 
       {
           count=H1 + L1 + (H1 - x1);
       }
       else if(x1==0) //一般情况: 
       {
           count=H1 + L1 + (H1 - x1) + (L1 - y1);
       }
       else  //出错情况: 
       {
           count= -1;
       }        return count;
   }    //计算并输出螺旋矩阵
   public void print()
   {
        System.out.println("H = " + H +" , " + "L = " + L);
        System.out.println("******************************************");
        for(int j=0;j<=L;j++)
        {
            for(int i=0;i<=H;i++)
            {
                System.out.print(getDotCount(i,j)+" ");
            }
            System.out.println();
        }
        System.out.println("************************************");
   }
}