当前位置：首页 > news >正文

Z字形扫描ccf

news 2026/7/1 0:07:53

一、Z 字形扫描规则总结（非常关键）

对于一个 n × n 矩阵：

所有元素都位于若干条副对角线上

副对角线编号：

d = 行号 i + 列号 j

范围：0 ~ 2n-2

扫描顺序：

按 d = 0 → 2n-2 依次扫描

每条对角线的遍历方向固定为：

从上到下（行递增）

即 i 从小到大

⚠️ 这正好和题目给的样例完全一致

二、以样例为例（4×4）

矩阵：

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

按 i + j 分组：

d 元素
0 (0,0) → 1
1 (0,1),(1,0) → 5,3
2 (0,2),(1,1),(2,0) → 3,7,9
3 (0,3),(1,2),(2,1),(3,0) → 9,5,4,7
4 (1,3),(2,2),(3,1) → 6,6,3
5 (2,3),(3,2) → 4,1
6 (3,3) → 3

拼接后正是：

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

三、Java 实现（推荐，O(n²)，n≤500 完全没问题）

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();int[][]a=newint[n][n];for(inti=0;i<n;i++){for(intj=0;j<n;j++){a[i][j]=sc.nextInt();}}StringBuildersb=newStringBuilder();// d = i + jfor(intd=0;d<=2*n-2;d++){for(inti=0;i<n;i++){intj=d-i;if(j>=0&&j<n){sb.append(a[i][j]).append(" ");}}}// 去掉末尾空格System.out.println(sb.toString().trim());}}

一、为什么你会得到这个“错误输出”？

你得到的是：

1 5 3 3 7 9 9 5 4 7 6 6 3 4 1 3

而正确答案是：

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

根本原因只有一句话：

题目中的“Z 字形扫描”不是“每条对角线都同方向”
而是“对角线方向交替变化”

我之前给你的代码是：

for (d = 0 … 2n-2)
for (i 从小到大)
输出 a[i][d-i]

👉 这叫单向对角线扫描
👉 不是题目要求的 Zigzag

二、真正的 Zigzag 规则（以题目为准）

仍然按：

d = i + j

分组，但遍历方向取决于 d 的奇偶性：

规则总结
d 的奇偶遍历方向
d 为偶数从下往上（i 大 → i 小）
d 为奇数从上往下（i 小 → i 大）

这才是 Z 字形的来源（方向来回折返）

三、用样例严格验证一遍（关键）
d = 2（偶数）

对角线元素：

(0,2)=3
(1,1)=7
(2,0)=9

偶数 ⇒ 反向输出：

9 7 3

✔️ 正确答案中正是这个顺序

d = 3（奇数）
(0,3)=9
(1,2)=5
(2,1)=4
(3,0)=7

奇数 ⇒ 正向输出：

9 5 4 7

✔️ 完全一致

四、修正后的正确 Java 代码 ✅

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();int[][]a=newint[n][n];for(inti=0;i<n;i++){for(intj=0;j<n;j++){a[i][j]=sc.nextInt();}}StringBuildersb=newStringBuilder();for(intd=0;d<=2*n-2;d++){if(d%2==0){// 偶数：从下往上for(inti=n-1;i>=0;i--){intj=d-i;if(j>=0&&j<n){sb.append(a[i][j]).append(" ");}}}else{// 奇数：从上往下for(inti=0;i<n;i++){intj=d-i;if(j>=0&&j<n){sb.append(a[i][j]).append(" ");}}}}System.out.println(sb.toString().trim());}}