首页 > 代码库 > 九度oj 题目1391:顺时针打印矩阵
九度oj 题目1391:顺时针打印矩阵
- 题目描述:
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵:
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.
- 输入:
输入可能包含多个测试样例,对于每个测试案例,
输入的第一行包括两个整数m和n(1<=m,n<=1000):表示矩阵的维数为m行n列。
接下来的m行,每行包括n个整数,表示矩阵的元素,其中每个元素a的取值范围为(1<=a<=10000)。
- 输出:
对应每个测试案例,输出一行,
按照从外向里以顺时针的顺序依次打印出每一个数字,每个数字后面都有一个空格。
- 样例输入:
4 41 2 3 45 6 7 89 10 11 1213 14 15 16
- 样例输出:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
这个题一开始是用哨兵的思想做的,在矩阵周围都设为0,碰到哨兵就转一个方向,开始设的哨兵值是0,结果一直超时,题目明明说 a >= 1的
只好设哨兵为-1了,代码如下1 #include <cstdio> 2 #include <cstring> 3 4 int matrix[1003][1003]; 5 int dir[][2] = {{0,1},{1,0},{0,-1},{-1,0}}; 6 7 int main(int argc, char const *argv[]) 8 { 9 int m, n;10 while(scanf("%d %d",&m,&n) != EOF) {11 for(int i = 0; i < 1003; i++) {12 for(int j = 0; j < 1002; j++) {13 matrix[i][j] = -1;14 }15 }16 17 for(int i = 1; i <= m; i++) {18 for(int j = 1; j <= n; j++) {19 scanf("%d",&matrix[i][j]);20 }21 }22 23 int tx = 1, ty = 0;24 int di = 0;25 int num = m*n;26 int cnt = 0;27 while(cnt < num) {28 tx = tx + dir[di][0];29 ty = ty + dir[di][1];30 while(matrix[tx][ty] != -1) {31 printf("%d ",matrix[tx][ty]);32 matrix[tx][ty] = -1;33 cnt++;34 tx = tx + dir[di][0];35 ty = ty + dir[di][1];36 }37 tx = tx - dir[di][0];38 ty = ty - dir[di][1];39 di = (di+1) % 4;40 41 }42 puts("");43 } 44 return 0;45 }
但是代码居然跑了980ms,
试着修改了一下,按四个方向判断输出
1 #include <cstdio> 2 #include <cstring> 3 4 int matrix[1003][1003]; 5 int dir[][2] = {{0,1},{1,0},{0,-1},{-1,0}}; 6 7 int main(int argc, char const *argv[]) 8 { 9 int m, n;10 while(scanf("%d %d",&m,&n) != EOF) {11 for(int i = 0; i < 1002; i++) {12 for(int j = 0; j < 1002; j++) {13 matrix[i][j] = -1;14 }15 }16 17 for(int i = 1; i <= m; i++) {18 for(int j = 1; j <= n; j++) {19 scanf("%d",&matrix[i][j]);20 }21 }22 23 int tx = 1, ty = 0;24 int di = 0;25 int num = m*n;26 int cnt = 0;27 while(cnt < num) {28 int i;29 for(i = ty+1; matrix[tx][i] != -1; i++) {30 printf("%d ",matrix[tx][i]);31 cnt++;32 matrix[tx][i] = -1;33 }34 ty = i-1;35 for(i = tx+1; matrix[i][ty] != -1; i++) {36 printf("%d ",matrix[i][ty]);37 cnt++;38 matrix[i][ty] = -1;39 }40 tx = i-1;41 for(i = ty-1; matrix[tx][i] != -1; i--) {42 printf("%d ",matrix[tx][i]);43 cnt++;44 matrix[tx][i] = -1;45 }46 ty = i+1;47 for(i = tx-1; matrix[i][ty] != -1; i--) {48 printf("%d ",matrix[i][ty]);49 cnt++;50 matrix[i][ty] = -1;51 }52 tx = i+1;53 }54 puts("");55 } 56 return 0;57 }
跑了940ms
考虑时间这么长,是不是赋值语句导致的,只好换了个思路,用普通的界限来判断输出了
1 #include <cstdio> 2 #include <cstring> 3 4 int matrix[1003][1003]; 5 6 int main(int argc, char const *argv[]) 7 { 8 int m, n; 9 while(scanf("%d %d",&m,&n) != EOF) {10 11 for(int i = 1; i <= m; i++) {12 for(int j = 1; j <= n; j++) {13 scanf("%d",&matrix[i][j]);14 }15 }16 17 int tx = 1, ty = 0;18 int num = m*n;19 int cnt = 0;20 int xt = m, yt = n, xf = 2, yf = 1;21 while(cnt < num) {22 int i;23 for(i = ty+1; i <= yt; i++) {24 printf("%d ",matrix[tx][i]);25 cnt++;26 }27 yt--;28 ty = i-1;29 if(cnt == num) {30 break;31 }32 for(i = tx+1; i <= xt; i++) {33 printf("%d ",matrix[i][ty]);34 cnt++;35 }36 xt--;37 tx = i-1;38 if(cnt == num) {39 break;40 }41 for(i = ty-1; i >= yf; i--) {42 printf("%d ",matrix[tx][i]);43 cnt++;44 }45 ty = i+1;46 yf++;47 if(cnt == num) {48 break;49 }50 51 for(i = tx-1; i >= xf; i--) {52 printf("%d ",matrix[i][ty]);53 cnt++;54 }55 tx = i+1;56 xf++;57 }58 puts("");59 } 60 return 0;61 }
时间果然变少,只花了500ms
九度oj 题目1391:顺时针打印矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。