CCF认证真题-(201412-2)-Z字形扫描

AntonLiu 2021-08-14 原文

思路1:

将每一条斜线作为一层, 可以证明一共有 n+n-1 层, 即 2*n-1 层. 再对每一层分别进行扫描. 扫描一层需要知道起点(终点通过起点、变换方式和矩形范围可以唯一确定)和扫描的方向(偶数层一个方向, 奇数层一个方向)

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int n;
 5 int arr[505][505]{0};
 6 
 7 void paintDia(int level, bool isEven)
 8 {
 9     int x = level > n - 1 ? n - 1 : level;
10     int y = level > n - 1 ? level - n + 1 : 0;
11     if (!isEven)
12         swap(x, y);
13 
14     while (x >= 0 && x < n && y >= 0 && y < n) {
15         if (x == n - 1 && y == n - 1)
16             cout << arr[x][y] << endl;
17         else
18             cout << arr[x][y] << \' \';
19 
20         if (isEven) {
21             x--;
22             y++;
23         }
24         else {
25             x++;
26             y--;
27         }
28     }
29 }
30 
31 int main()
32 {
33     ios::sync_with_stdio(false);
34     cin.tie(0);
35 
36     cin >> n;
37     for (int i = 0; i < n; i++)
38         for (int j = 0; j < n; j++)
39             cin >> arr[i][j];
40 
41     for (int l = 0; l < 2 * n - 1; l++)
42         paintDia(l, l % 2 == 0);
43 
44     return 0;
45 }

思路2:

也可以将上三角和下三角分开处理.

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int n;
 5 int arr[505][505];
 6 bool flag;
 7 
 8 void printComp(int x1, int y1, int x2, int y2)
 9 {
10     int i = x1, j = y1;
11     if (x1 == n && x2 == n) {
12         cout << arr[n][n] << endl;
13         return;
14     }
15     if (!flag) {
16         // 斜向上
17         while (i >= 1 && j <= y2) {
18             cout << arr[i][j] << \' \';
19             i--;
20             j++;
21         }
22     }
23     else {
24         // 斜向下
25         while (i <= x2 && j >= 1) {
26             cout << arr[i][j] << \' \';
27             i++;
28             j--;
29         }
30     }
31 }
32 
33 int main()
34 {
35     ios::sync_with_stdio(false);
36     cin.tie(0);
37 
38     cin >> n;
39     for (int i = 1; i <= n; i++)
40         for (int j = 1; j <= n; j++)
41             cin >> arr[i][j];
42             
43     flag = false;
44     for (int i = 1; i <= n; i++) {
45         if (!flag) printComp(i, 1, 1, i);
46         else printComp(1, i, i, 1);
47         flag = !flag;
48     }
49     for (int i = 2; i <= n; i++) {
50         if (!flag) printComp(n, i, i, n);
51         else printComp(i, n, n, i);
52         flag = !flag;
53     }
54 
55     return 0;
56 }