Z字形扫描

Sat May 09 23:00:55 CST 2015 6628 算法

文章摘要 在图像编码的算法中,需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。请实现一个Z字形扫描的程序,给定一个n×n的矩阵,输出对这个矩阵进行Z字形扫描的结果。

题目

题目详细如下:(来源自http://bbs.csdn.net/topics/390953265,好惊奇的帖子,不知道是哪位同学在考试期间居然能发帖到CSDN,让我有幸复制到考试原文。此外http://www.0531s.com/content-53-1928772-1.html有转发)


在图像编码的算法中,需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵,Z字形扫描的过程如下图所示:

  对于下面的4×4的矩阵,
  1 5 3 9
  3 7 5 6
  9 4 6 4
  7 3 1 3
  对其进行Z字形扫描后得到长度为16的序列:
  1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
  请实现一个Z字形扫描的程序,给定一个n×n的矩阵,输出对这个矩阵进行Z字形扫描的结果。
输入格式
  输入的第一行包含一个整数n,表示矩阵的大小。
  输入的第二行到第n+1行每行包含n个正整数,由空格分隔,表示给定的矩阵。
输出格式
  输出一行,包含n×n个整数,由空格分隔,表示输入的矩阵经过Z字形扫描后的结果。
样例输入
4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3
样例输出
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
评测用例规模与约定
  1≤n≤500,矩阵元素为不超过1000的正整数。

------------------------------------------------------------------------------------------------------------------------------


分析

考完试回来上网搜了搜矩阵Z字形扫描,网上不少高手有先进的解法。这里我就不多说了。大家可以去百度或者谷歌。


我在这里分享下我考试时想到的比较直接的解法,略显笨拙。记得题目给的运算时间和运行空间还是比较宽松的。


在CCF认证考试的五道题里面,该题排在第二的位置,显然难度不是很大的,不宜恋战,应当速战速决。

考试当时想到的第一步就是看图找规律。发现矩阵Z字形扫描从(0,0)位置开始,前进的方向有4个,分别是右、下,左下、右上。不难看出,Z字形扫描向右、向下两个方向,只前进一步就会变向,改变后的方向因情况而异;而左下和右上两个方向则会一直延伸,直至前面无法继续直行时再变向为向右或者向下。

然而值得注意的时:

1.左下方向因无法继续直行需要变向时,要先判断是否能往下走,若不能往下走再往右走;

2.右上方向因无法继续直行需要变向时,要先判断是否能往右走,若不能往右走再往下走。

到这里可以总结出:下一步的方向,由上一步的方向以及周围的情况(是否临界)决定。


想到这些,我就想模拟一个人在(0,0)这个位置出发,沿题目要求的路径走到(n-1,n-1)的位置。由于下一步的方向需要上一步的方向来参与决策,因此需要引入一个方向变量direction,分别用值1,2,3,4代表4个方向:右,下,左下,右上。编程的时候可以分解为两个步骤: 

1.根据上一步的方向以及是否到达边界位置来决定下一步方向;

2.根据步骤1得到的方向前进一步,读取该位置的数字。

循环直至到达终点(n-1, n-1)


说到这里,相信看下面的代码就能看懂了(为了更容易看懂一些,有一部分代码可以简化的没有简化)


代码

(CCF认证考试对JAVA语言答题的要求:1.程序入口为Main类的main方法;2.不能有package;3.输入System.in,输出System.out)

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.Scanner;
 
public class Main {
 
    //下面四个变量代表四个方向
    public static final int RIGHT = 1;    //向右走
    public static final int DOWN = 2; //向下走
    public static final int LEFTDOWN = 3; //向做下走
    public static final int RIGHTUP = 4//向右上走
     
    public static int data[][];            //矩阵
     
    public static void main(String[] args) {
        new Main().run();
    }
     
    public static void run(){
        //接收输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        data = new int[n][n];
         
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                data[i][j] = scanner.nextInt();
            }
        }
         
        //从第一个位置开始,x为横坐标,y为纵坐标,注意x,y在二维数组中的位置
        int x = 0;
        int y = 0;
        //输出要求有空格隔开
        String result = data[y][x] + " ";
        //方向变量的初始值
        int direction = 0;  
         
        //下面就开始出发走咯
        while( !(x == n-1 && y == n-1) ){//循环直至到达终点(最右下角的位置)
            //先判断下一步往哪个方向走
            if(direction == 0){   //为0说明还没走出第一步,所以接着应该往右边走一步
                direction = RIGHT;
            else if(direction == RIGHT){ //上一次方向向右,下一步应该向左下或者右上
                if(x-1 >= 0 && y+1 < n){    //左下可走
                    direction = LEFTDOWN;
                else //只能走右上了
                    direction = RIGHTUP;
                }
            else if(direction == DOWN){   //上一次方向向下,下一步应该向左下或者右上
                if(x-1 >= 0 && y+1 < n){    //左下可走
                    direction = LEFTDOWN;
                else //只能走右上了
                    direction = RIGHTUP;
                }
            else if(direction == LEFTDOWN){   //上一次向左下,如果可以,下一步应该继续向左下,否则 向右或者向下走
                if(y+1 < n && x-1 >= 0){    //先判断能否继续向左下
                    direction = LEFTDOWN;
                else if(y+1 < n){  //然后判断能否向下走
                    direction = DOWN;
                else {      //最后只能向右走了
                    direction = RIGHT;
                }
            else if(direction == RIGHTUP){    //上一次向右上,如果可以,下一步应该继续向右上,否则向右或者下走
                if(x+1 < n && y-1 >=0){  //先判断能否继续向右上
                    direction = RIGHTUP;
                else if(x+1 < n){  //然后判断能否向右走
                    direction = RIGHT;
                else{            //最后只能向下走了
                    direction = DOWN;
                }
            }
             
            //根据上面确定的方向来走出下一步
            switch(direction){
                case RIGHT: x = x+1break;
                case DOWN: y = y+1break;
                case LEFTDOWN: x = x-1; y = y+1break;
                case RIGHTUP: x = x+1; y = y-1break;
            }
             
            //读取当前走到位置的数字.注意x和y的位置
            result += data[y][x] + " ";
        }
         
        //输出结果(这里需不需要去掉最后的空格?没怎么玩过ACM,不记得了acc格式控制会不会这么严)
        System.out.println(result);
    }
 
}




打赏
打赏

分享到: