PrintMatrix

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/39/]

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

样例

1
2
3
4
5
6
7
8
输入：
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]

输出：[1,2,3,4,8,12,11,10,9,5,6,7]

算法描述

常规操作，走地图的题相当于，定义移动的结构dx = {0,1,0,-1},dy=[1,0,-1,0]每一个元素都给一个标识，用布尔型记录是否被访问过，每次碰到边界条件就转向一次，直到所有的元素都被访问到结束；

需要转向的条件：1.超矩阵范围；2.要走的方向的节点被访问

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.empty())return res;
        int n=matrix.size(),m=matrix[0].size();
        vector<vector<bool>> bl(n,vector<bool>(m,false));
        int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
        int x=0,y=0,d=0;
        for(int i=0;i<n*m;i++){
            res.push_back(matrix[x][y]);
            bl[x][y]=true;
            
            int a=x+dx[d],b=y+dy[d];
            if(a<0||a>=n||b<0||b>=m||bl[a][b]){
                d=(d+1)%4;
                a=x+dx[d],b=y+dy[d];
            }
            x=a,y=b;
        }
        return res;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] printMatrix(int[][] matrix) {
        int m = matrix.length;
        if(m==0)return new int[0];
        int n = matrix[0].length;
        if(n==0)return new int[0];
        List<Integer> res = new ArrayList<>();
        boolean[][] flag = new boolean[m][n];
        int x=0,y=0,d=0;
        int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
        for(int i=0;i<n*m;i++){
           res.add(matrix[x][y]);
           flag[x][y]=true;
           int a = x+dx[d],b = y+dy[d];
           if(a<0||a>=m||b<0||b>=n||flag[a][b]==true){
               d=(d+1)%4;
               a = x+dx[d];
               b = y+dy[d];
           }
           x = a;
           y = b;
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}