简书是一个不错的平台，可是种类繁杂，毕竟不是一个专属于程序员的博客平台，一直很犹豫是否要把博客从CSDN转移到这里来。最终还是抵挡不了平台的诱惑啊。不过说到底，写在哪里都一样，写下来能够加深自己的印象，同时能够给一些要学的人一些干货，何乐而不为。那么，就从一道算法题目开始吧。

顺时针填充矩阵

题目：
给出一个二维数组，要求按照顺时针将二维数组从1~n填充。
例如：4*4的二维数组，填充之后为：

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

题解：
这道题的解题思路有很多，我只在这里说明一种解法：使用回溯算法求解。所谓回溯算法，实际上是一种向前探索的思路。它会在求解的时候向前探索，把可能出现的情况作为路径，当这条路无法得到结果时，它会回过头，探索下一条可能出现的情况。
那么思路如下：首先，矩阵要实现顺时针填充，必须要有一个控制方向的“方向盘”。如例子中的矩阵，当一开始向前填充数字的时候，没有方向的控制，结果只能是下标越界。当有了“方向盘”之后，数字的填充还需要第二个东西，就是“转弯指示器”。当数字填充到数组边界时，“转弯指示器”会提醒“方向盘”转弯。第三，也就是在数组填充完成后，停止的判断了。

我们可以把以上思路先用伪代码表示如下

//0、初始的方向为向右，开始坐标为（1,1）
//1、当前坐标为（x,y），方向为：dir。“填充者”开始工作，填充数字。
     向坐标（x,y）填入当前数字。
//2、转弯指示器和停止判断器开始工作，判断是否到达边界需要转弯，
     以及是否填充完成需要停止。转弯，执行第5步；停止，执行return。
     否则坐标沿着方向指向向接下来的位置移动，
     即改变（x,y），然后执行第1步。
//4、转弯：方向顺时针改变一步，然后然后坐标按照当前更改过的方向移动，执行步骤1。

那么，“转弯指示器”如何设置呢？
我们可以设置这样一个数组：
int move[][] = {{0,1},{1,0},{0,-1},{-1,0}};
以及这样一个指针下标：
int direction = 0;
当direction的值为0,1,2,3时，分别对应move数组的4个一维数组，用以表示右、下、左、上四个方向。那么如何在程序中使用这个方向指示器呢？完整代码如下：

import java.util.Scanner;
public class Main {
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //输入数字n，设置n*n的数组
        CreateA(n);
      } 
      public static void CreateA(int n){
      //初始化矩阵为长宽n+2的二维数组，最外层一圈填值为0，其余为-1
        int[][] a = new int[n+2][n+2];
        for (int i = 1; i < a.length-1; i++) {
            for (int j = 1; j < a[i].length-1; j++) {
                a[i][j] = -1;
            }
        }
        //方向数组 该数组为本算法的关键
        int move[][] = {{0,1},{1,0},{0,-1},{-1,0}};
        int direction = 0;
        int k= 1;
        Go(k, 1, 1, n, a, move, direction);
        //输出填好的蛇形矩阵
        for (int i = 1; i < a.length-1; i++) {
            for (int j = 1; j < a[i].length-1; j++) {
                System.out.print("\t"+a[i][j]);
            }
            System.out.println();
        }
      }
//  填写矩阵，矩阵最外层的一圈为0，其他值为-1，当遇到-1的时候才给矩阵里填值
      public static void Go(int k,int x,int y,int n,int a[][],int move[][],int direction){
          a[x][y]  = k++;
          if(k> n*n)
              return;
          while(a[x+move[direction][0]][y+move[direction][1]]!= -1){
          //方向由 右、下、左、上循环
              direction = (direction+1)%4;
          }
          //x,y为即将走上的下一个格子
          x = x+move[direction][0];
          y = y+move[direction][1];
          Go(k, x, y, n, a, move, direction);
      }
}