逆时针矩阵

最近在http://suanfa.group.iteye.com/group/topic/27110看到一个逆时针矩阵。大致意思是说如果给定M*N的矩阵，在矩阵中采用逆时针方式填充数据。比如

3*3矩阵结果是：
1  8  7
2  9  6
3  4  5
3*4矩阵结果是：
1 10  9  8
2 11 12  7
3  4  5  6
4*6矩阵结果是：
1 16 15 14 13 12
2 17 24 23 22 11
3 18 19 20 21 10
4  5  6  7  8  9
6*4矩阵结果是：
1 16 15 14
2 17 24 13
3 18 23 12
4 19 22 11
5 20 21 10
6  7  8  9

这种问题首先想到的是个数学问题，最好的办法是总结出规律，直接定位。如
f(x,y)=z （其中x,y是矩阵的坐标，z是对应的数值，如 f(2,3)=19表示第3行第4列的值是19），只要找到这样的f函数即可。

另外这个方法符合递归的特性，比如最外面一圈的数据（一个长方形）与第二圈的数据（也是一个长方形）有相同的特性，都是按“下-->右-->上-->左”的方式填充的，左上角数据最小，第一行第二个数据最大，...。这样就可以用递归的方式来实现了“先填充外层矩形，如果矩形不是空心的，再递归填充里面的矩阵”。

还有一种方法是按题目的说法（逆时针输出），用模拟的方法来实现，“当前位置填充--->找到下一位置--->当前位置填充--->找到下一位置-->...”由于数据是连续的，每次只要找到“下一个填充位置”就可以了。下一位置怎么找？与当前填充方向有关。即有4种填充策略，每个填充完后返回下一个要使用的策略。

实际应用中应该优先考虑第一种方法，这样效率极高。
第二种方法也还可以，代码应该会比较简洁。
我这里对第三种方法进行了尝试，完整代码如下

public class Dir {
    public class Position{
        public int row; 
        public int col; 
        public Position(int row,int col){
            this.row=row;
            this.col=col;
        }
    }
    public static final Dir DOWN=new Dir(){
        protected Dir getNext() {
            return Dir.RIGHT;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.row++;
            //从当前位置往下填充所有为0的单元格，遇到不为0（表示已经填充过了）时停止
            for(int i=pos.row,len=arr.length;i<len;i++){
                if(arr[i][pos.col]==0){
                    arr[i][pos.col]=++temp;
                    pos.row=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public static final Dir RIGHT=new Dir(){
        protected Dir getNext() {
            return Dir.UP;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.col++;
            //从当前位置往右填充所有为0的单元格，遇到不为0（表示已经填充过了）时停止
            for(int i=pos.col,len=arr[0].length;i<len;i++){
                if(arr[pos.row][i]==0){
                    arr[pos.row][i]=++temp;
                    pos.col=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public static final Dir UP=new Dir(){
        protected Dir getNext() {
            return Dir.LEFT;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.row--;
            //从当前位置往上填充所有为0的单元格，遇到不为0（表示已经填充过了）时停止
            for(int i=pos.row;i>=0;i--){
                if(arr[i][pos.col]==0){
                    arr[i][pos.col]=++temp;
                    pos.row=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public static final Dir LEFT=new Dir(){
        protected Dir getNext() {
            return Dir.DOWN;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.col--;
            //从当前位置往左填充所有为0的单元格，遇到不为0（表示已经填充过了）时停止
            for(int i=pos.col;i>=0;i--){
                if(arr[pos.row][i]==0){
                    arr[pos.row][i]=++temp;
                    pos.col=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public Dir fill(int[][] arr,Position pos){
        return null;// to be implemented
    }
    /** 下一个方向是什么 */
    protected Dir getNext() {
        return null;// to be implemented
    }
    protected Dir nextDir(int[][] arr,Position pos){
        return (arr[pos.row][pos.col]==arr.length*arr[0].length)?null:this.getNext();
    }
    
}

测试代码如下

public class Test {

    public static void main(String[] args) {
        // 4行6列的数组
        int M = 4, N = 6;
        int[][] arr = new int[M][N];
        arr[0][0] = 1;
        //初始方向向下
        Dir d = Dir.DOWN;
        //初始位置左上角
        Position pos = d.new Position(0,0);
        //开始填充
        do {
            d = d.fill(arr, pos);
        } while (d != null);
        //输出结果
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print((arr[i][j] < 10 ?" ":"")+arr[i][j]+" ");
            }
            System.out.println();
        }
    }
}

运行结果为:
1 16 15 14 13 12
2 17 24 23 22 11
3 18 19 20 21 10
4  5  6  7  8  9
完全正常。

以上代码中使用了“模板方法模式+变种的单例模式（4个实例）”。还有“匿名内部类”的使用。

评论

2 楼 mfkvfn 2012-03-26  

实际工程中没有意义，纯学术研究，可能跟游戏方面有一点点沾边。

1 楼 handy.wang 2012-03-24  

这个能解决工程中什么实际问题呢？我比较关心这个。
如果是纯学术没有意义。