首页 > 代码库 > 51. 顺时针打印矩阵[print matrix in clockwise direction]

51. 顺时针打印矩阵[print matrix in clockwise direction]

2024-07-05 20:05:37   230人阅读

【题目】

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

例如：如果输入如下矩阵：

1            2            3            4

5            6            7            8

9            10          11           12

13          14          15           16

则依次打印出数字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。

【分析】

解决这道题的难度在于代码中会包含很多个循环，而且还有多个边界条件需要判断。如果在把问题考虑得很清楚之前就开始写代码，不可避免地会越写越混乱。因此解决这个问题的关键，在于先要形成清晰的思路，并把复杂的问题分解成若干个简单的问题。

通常当我们遇到一个复杂的问题的时候，我们可以用图形帮助我们思考。由于我们是以从外圈到内圈的顺序依次打印，我们在矩阵中标注一圈作为我们分析的目标。在下图中，我们设矩阵的宽度为columns，而其高度为rows。我们我们选取左上角坐标为(startX, startY)，右下角坐标为(endX, endY)的一个圈来分析。

由于endX和endY可以根据startX、startY以及columns、rows来求得，因此此时我们只需要引入startX和startY两个变量。我们可以想象有一个循环，在每一次循环里我们从(startX, startY)出发按照顺时针打印数字。

【代码】

 C++ Code 
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
  
// 51_PrintMatrixInClockwiseDirection.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

// print number
void PrintNumber(int number)
{
     printf("%d ", number);
}

// print matrix normally
void PrintMatrix(int **a, int columns, int rows)
{
    for (int i = 0; i < rows; i++)
     {
        for (int j = 0; j < columns; j++)
         {
             printf("%d\t", a[i][j]);
         }
         printf("\n");
     }
}

/*
   sx,sy--------------ex,sy
     |                             |
     |                             |
     |                             |
   sx,ey--------------ex,ey
*/
// print numbers in 4 directions
void PrintNumbersInCircle(int **a, int columns, int rows, int sx, int sy)
{
    // a[y][x]
    int ex = columns - 1 - sx;
    int ey = rows - 1 - sy;
    int i;

    // case1
    // sx,sy---ex,sy
    // a[sy][i]
    bool b1 = sx <= ex;
    bool b2 = sy < ey;
    bool b3 = sx < ex;
    bool b4 = sy < ey - 1;
    if(b1)
     {
        // case1 matches b1
        for (i = sx; i <= ex; ++i)
         {
            int number = a[sy][i];
             PrintNumber(number);
         }
     }

    //case2
    // ex,sy+1---ex,ey
    // a[i][ex]
    if(b1 && b2)
     {
        // case2 matches b1,b2
        for (i = sy + 1; i <= ey; ++i)
         {
            int number = a[i][ex];
             PrintNumber(number);
         }
     }

    //case3
    // ex-1,ey---sx,ey
    // a[ey][i]
    if(b1 && b2 && b3)
     {
        // case3 matches b1,b2,b3
        for (i = ex - 1; i >= sx; --i)
         {
            int number = a[ey][i];
             PrintNumber(number);
         }
     }

    //case4
    // sx,ey-1---sx,sy+1
    // a[i][sx]
    if(b1 && b2 && b3 && b4)
     {
        // case4 mathces b1,b2,b3,b4
        for (i = ey - 1; i >= sy + 1; --i)
         {
            int number = a[i][sx];
             PrintNumber(number);
         }
     }
}

/*
print matrix in clockwise direction
by hellogiser 2014/5/23
*/
void PrintMatrixInClockwiseDirection(int **a, int columns, int rows)
{
    if(NULL == a || columns <= 0 || rows <= 0)
        return;
    int startx = 0;
    int starty = 0;
    while(2 * startx < columns && 2 * starty < rows)
     {
         PrintNumbersInCircle(a, columns, rows, startx, starty);
         startx++;
         starty++;
     }
}

void test_base(int **a, int columns, int rows)
{
     PrintMatrix(a, columns, rows);
     PrintMatrixInClockwiseDirection(a, columns, rows);
     printf("\n");
}

void test_case()
{
    const int ROWS = 4;
    const int COLUMNS = 4;
    int a[ROWS][COLUMNS];
    for (int i = 0; i < ROWS; i++)
        for (int j = 0; j < COLUMNS; j++)
             a[i][j] = i * COLUMNS + j + 1;

    int *p[ROWS];
    for (int i = 0; i < ROWS; i++)
         p[i] = a[i];

    int **array = p;

     test_base(array, COLUMNS, ROWS);
}

void test_main()
{
     test_case();
}

int _tmain(int argc, _TCHAR *argv[])
{
     test_main();
    return 0;
}
/*
//case1
[3*5]
1       2       3       4       5
6       7       8       9       10
11      12      13      14      15
1 2 3 4 5 10 15 14 13 12 11 6 7 8 9

//case2
[5*3]
1       2       3
4       5       6
7       8       9
10      11      12
13      14      15
1 2 3 6 9 12 15 14 13 10 7 4 5 8 11

//case3
[4*5]
1       2       3       4       5
6       7       8       9       10
11      12      13      14      15
16      17      18      19      20
1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12

//case4
[5*4]
1       2       3       4
5       6       7       8
9       10      11      12
13      14      15      16
17      18      19      20
1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10
*/

【参考】

http://zhedahht.blog.163.com/blog/static/254111742010111112236313/

http://www.cnblogs.com/python27/archive/2011/11/29/2267975.html


联系
我们