【牛客题霸题解】螺旋矩阵

先列举几种情况

观察一下，思路其实可以归纳为从起点(0,0)开始
先往左走，没有办法往左走了（到了边界或者是左边的格子已经走过了）就往下走，
不能往下走了以后就往右走，
不能往右走了以后就往上走，
不能往上走了以后就往左走。
直到有一个格子四个方向都不能走了，就结束循环。
所以我们设立一个visit数组，visit[i][j]表示(i,j)位置之前有没有访问过
然后建立dir数组，来表示当前的方向，如果当前方向不能走了，用(t+1)%4就可以进行以上的变换了。
c++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ans;
        int m = matrix.size();
        if(m==0){ return ans; }
        int n = matrix[0].size();
        if(n==0){ return ans; }
        vector<vector<bool> > visit(m);
        for(int i = 0 ; i < m ; i++) { visit[i].resize(n); }
        int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
        int t = 0;//走哪个方向，0右 1下 2左 3上
        int x = 0,y = 0;
        bool end = false;
        while(!end)
        {
            ans.push_back(matrix[x][y]);
            visit[x][y] = true;
            for(int i = 0 ; i < 5 ; i++)//如果现在的位置四个方向都不能走了，循环就可以结束了。
            {
                if(i == 4){end = true;break;}
                int tx = x + dir[t][0];
                int ty = y + dir[t][1];
                if(tx >= 0 && tx < m && ty >= 0 && ty < n && !visit[tx][ty])
                {
                    x = tx;
                    y = ty;
                    break;
                }
                else{//失败了，换方向走
                    t = (t+1)%4;
                }
            }
        }
        return ans;
    }
};

java

import java.util.*;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        int m = matrix.length;
        if(m==0){ return ans; }
        int n = matrix[0].length;
        if(n==0){ return ans; }
        boolean[][] visit = new boolean[m][n];
        int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};
        int t = 0;//走哪个方向，0右 1下 2左 3上
        int x = 0,y = 0;
        boolean end = false;
        while(!end)
        {
            ans.add(matrix[x][y]);
            visit[x][y] = true;
            for(int i = 0 ; i < 5 ; i++)//如果现在的位置四个方向都不能走了，循环就可以结束了。
            {
                if(i == 4){end = true;break;}
                int tx = x + dir[t][0];
                int ty = y + dir[t][1];
                if(tx >= 0 && tx < m && ty >= 0 && ty < n && !visit[tx][ty])
                {
                    x = tx;
                    y = ty;
                    break;
                }
                else{//失败了，换方向走
                    t = (t+1)%4;
                }
            }
        }
        return ans;
    }
}

python

class Solution:
    def spiralOrder(self , matrix ):
        ans = []
        m = len(matrix)
        if m==0:
            return ans
        n = len(matrix[0])
        if n==0:
            return ans
        visit = [[False for i in range(n)] for j in range(m)]
        dir =[[0,1],[1,0],[0,-1],[-1,0]]
        t = 0#走哪个方向，0右 1下 2左 3上
        x = 0
        y = 0
        end = False
        while end==False:
            ans.append(matrix[x][y])
            visit[x][y] = True
            for i in range(0,5):#如果现在的位置四个方向都不能走了，循环就可以结束了。
                if i == 4:
                    end = True
                    break
                tx = x + dir[t][0]
                ty = y + dir[t][1]
                if tx >= 0 and tx < m and ty >= 0 and ty < n and visit[tx][ty]==False:
                    x = tx
                    y = ty
                    break
                else:#失败了，换方向走
                    t = (t+1)%4;
        return ans