首页 > 代码库 > 九度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:顺时针打印矩阵