转圈打印矩阵
题目描述
给定一个整型矩阵matrix，请按照顺时针转圈的方式打印它。
输入描述：
输入包含多行，第一行两个整数n和m
(
1
≤
n
,
m
≤
200
)
(1 \leq n,m \leq 200)
(1≤n,m≤200)，代表矩阵的行数和列数，接下来n行，每行m个整数，代表矩阵
m
a
t
r
i
x
(
1
≤
m
a
t
r
i
x
[
i
]
[
j
]
≤
1
0
5
)
matrix(1 \leq matrix[i][j] \leq 10^5)
matrix(1≤matrix[i][j]≤105)。
输出描述：
输出包含一行，n*m个整数，代表顺时针转圈输出的矩阵matrix。
示例1
输入
4 4
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
备注：
额外空间复杂度O(1)
题解：
蛇形矩阵打印有很多方法，无非是按照向右，向下，向左，向上的顺序模拟，一般解法需要额外使用一个数组记录每个位置是否被填充过。但此题要求额外空间复杂度为
O
(
1
)
O(1)
O(1) ，上面的解法就不适用了。如何做呢？
我们可以使用左上角和右下角两个点来描述一个子矩阵，那么我们可以每次将子矩阵最外层打印，然后减小子矩阵，就这样层层剥开原矩阵即可。
代码：
#include <cstdio>
using namespace std
;
const int N
= 200;
int n
, m
;
int a
[N
][N
];
int main(void) {
scanf("%d%d", &n
, &m
);
for ( int i
= 0; i
< n
; ++i
) {
for ( int j
= 0; j
< m
; ++j
)
scanf
( "%d", a
[i
] + j
);
}
int tot
= n
* m
;
int now
= 0;
int tr
= 0, tc
= 0;
int dr
= n
- 1, dc
= m
- 1;
while ( now
< tot
) {
for ( int i
= tc
; i
<= dc
; ++i
) {
if ( now
++ ) putchar( ' ' );
printf("%d", a
[tr
][i
]);
}
for ( int i
= tr
+ 1; i
<= dr
; ++i
) {
if ( now
++ ) putchar( ' ' );
printf("%d", a
[i
][dc
]);
}
if ( tr
< dr
) {
for ( int i
= dc
- 1; i
>= tc
; --i
) {
if ( now
++ ) putchar( ' ' );
printf("%d", a
[dr
][i
]);
}
}
if ( tc
< dc
) {
for ( int i
= dr
- 1; i
> tr
; --i
) {
if ( now
++ ) putchar( ' ' );
printf("%d", a
[i
][tc
]);
}
}
++tc
, ++tr
;
--dc
, --dr
;
}
return 0 * puts("");
}
