Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

For example,

Given n = 3,

You should return the following matrix:

[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]] 继续DFS

1 class Solution { 2 private: 3     int step[4][2]; 4     bool canUse[100][100]; 5 public: 6     void dfs(int dep, vector
     
      
        > &matrix, int direct, int x, int y) 7     { 8         for(int i = 0; i < 4; i++) 9         {10             int j = (direct + i) % 4;11             int tx = x + step[j][0];12             int ty = y + step[j][1];13             if (0 <= tx && tx < matrix.size() && 0 <= ty && ty < matrix[0].size() && canUse[tx][ty])14             {15                 canUse[tx][ty] = false;16                 matrix[tx][ty] = dep;              17                 dfs(dep + 1, matrix, j, tx, ty);               18             }            19         }20     }21     22     vector
       
        
          > generateMatrix(int n) {23         // Start typing your C/C++ solution below24         // DO NOT write int main() function25         step[0][0] = 0;26         step[0][1] = 1;27         step[1][0] = 1;28         step[1][1] = 0;29         step[2][0] = 0;30         step[2][1] = -1;31         step[3][0] = -1;32         step[3][1] = 0;33         vector
         
          
            > ret(n, vector
           
            (n));34 memset(canUse, true, sizeof(canUse));35 dfs(1, ret, 0, 0, -1);36 37 return ret; 38 }39 40 };