关于螺旋矩阵问题的新思路

网上偶然看到一个笔试题，是关于螺旋矩阵的，题目如下：

输入一个矩阵的行列数量，生成一个螺旋矩阵，比如输入3,5，则打印：
   1       2      3     4     5
   12    13    14   15    6
   11     10    9     8     7
输入3,3，则打印：
   1        2        3
   8        9        4
   7        6        5

我用面向对象的思路，设计了一个蚂蚁在棋盘上爬行的模型，给出了行列相同时的解法，代码如下：

package org.unicorn.algorithms;


public class AntGame {

	public static void main(String[] args) {
		
		int m = 6;
		
		AntMap antMap = new AntMap(m);
		
		Ant ant = new Ant(antMap);
		
		Position curPos = new Position();
		
		int count = 1;
		
		while(count <= m * m) {
			
			ant.action(curPos, count++);
		}
		
		antMap.print();
	}
}

class AntMap {
	
	private int size;
	
	int[][] matrix;
	
	AntMap(int size) {
		this.size = size;
		matrix = new int[size][size];
	}
	
	int getSize() {
		return this.size;
	}
	
	void print() {
		
		for(int i = 0; i < size; ++ i) {
			
			for(int j = 0; j < size; ++ j) {
				
				System.out.format("%d ", matrix[i][j]);
			}
			
			System.out.println();
		}
	}
}

enum Action {
	
	FORWARD, BACKWARD, UP, DOWN
}

class Position {
	
	int row;  // 横坐标
	int col;  // 纵坐标
}

class Ant {
	
	AntMap map = null;

	Action curAction = Action.DOWN;
	
	Ant(AntMap map) {
		this.map = map;
	}
	
	void action(Position pos, int count) {
		
		map.matrix[pos.row][pos.col] = count;
		
		if(shouldTurn(pos)) {
			turn();
		}
		
		if(curAction == Action.FORWARD) {
			forward(pos);
		} else if(curAction == Action.DOWN) {
			down(pos);
		} else if(curAction == Action.BACKWARD) {
			backward(pos);
		} else if(curAction == Action.UP) {
			up(pos);
		}
	}
	
	private boolean shouldTurn(Position pos) {
		
		int min = 0;
		int max = map.getSize() - 1;
		
		if(curAction == Action.FORWARD) {
			
			if(pos.col >= max) {
				return true;
			} else if(map.matrix[pos.row][pos.col + 1] > 0) {
				return true;
			}
		} else if(curAction == Action.DOWN) {
			
			if(pos.row >= max) {
				return true;
			} else if(map.matrix[pos.row + 1][pos.col] > 0) {
				return true;
			}
		} else if(curAction == Action.BACKWARD) {
			
			if(pos.col <= min) {
				return true;
			} else if(map.matrix[pos.row][pos.col - 1] > 0) {
				return true;
			}
		} else if(curAction == Action.UP) {
			
			if(pos.row <= min) {
				return true;
			} else if(map.matrix[pos.row - 1][pos.col] > 0) {
				return true;
			}
		}
		
		return false;
	}
	
	private void turn() {
		
		if(curAction == Action.FORWARD) {
			curAction = Action.UP;
		} else if(curAction == Action.DOWN) {
			curAction = Action.FORWARD;
		} else if(curAction == Action.BACKWARD) {
			curAction = Action.DOWN;
		} else if(curAction == Action.UP) {
			curAction = Action.BACKWARD;
		}
	}

	private void forward(Position pos) {
		
		if(pos != null) {
			
			pos.col ++;
		}
	}

	private void backward(Position pos) {
		
		if(pos != null) {
			
			pos.col --;
		}
	}

	private void up(Position pos) {
		
		if(pos != null) {
			
			pos.row --;
		}
	}

	private void down(Position pos) {
		
		if(pos != null) {
			
			pos.row ++;
		}
	}
}

我觉得行列不同时也应该能够用该模型解决，只是转向规则复杂些。

这道题我是没想太多。直接用数组，填最外面一圈。圈子缩小，再填一圈…………圈子缩小，再填一圈。
=============
填到最后，就两种情况。一行多列，两行多列。

我也只是用数组，横的到尽头时纵的高度减1，方向改变；纵的到尽头时横的长度减1，方向改变。到0时停止

呃，我是这样做的。

 

上图的缩略图显示不全，你点击看完整图片

楼主的代码不太面向对象，太多if else了。帮楼主重构了一下，并补上了行列不同的功能。
java enum是很好用的：

public class AntGame {

	public static void main(String[] args) {
		int rowSize = 5;
		int colSize = 3;
		AntMap antMap = new AntMap(rowSize, colSize);
		Ant ant = new Ant(antMap);
		Position position = new Position(0,0);
		int count = 1;
		while (count <= colSize * rowSize) {
			ant.crawl(position, count++);
		}
		antMap.print();
	}
}

class AntMap {

	int[][] matrix;
	int rowSize;
	int colSize;
	
	AntMap(int rowSize, int colsize) {
		this.rowSize = rowSize;
		this.colSize = colsize;
		matrix = new int[rowSize][colsize];
	}

	void print() {
		for (int i = 0; i < rowSize; ++i) {
			for (int j = 0; j < colSize; ++j) 
				System.out.format("%3d", matrix[i][j]);
			System.out.println();
		}
	}
	public boolean isFilled(Position position) {
		return matrix[position.row][position.col] != 0;
	}
}

enum Action {
	
	FORWARD {
		public void act(Position position) {
			position.col++;
		}

		public boolean shouldTurn(Position position, AntMap antMap) {
			return position.col == antMap.colSize-1
				|| antMap.isFilled(position.nextCol());
		}
	}, 
	DOWN {
		public void act(Position position) {
			position.row++;
		}
		
		public boolean shouldTurn(Position position, AntMap antMap) {
			return position.row == antMap.rowSize-1
				|| antMap.isFilled(position.nextRow());
		}
	},
	BACKWARD {
		public void act(Position position) {
			position.col--;
		}

		public boolean shouldTurn(Position position, AntMap antMap) {
			return position.col == 0 
				|| antMap.isFilled(position.previousCol());
		}
	}, 
	UP {
		public void act(Position position) {
			position.row--;
		}

		public boolean shouldTurn(Position position, AntMap antMap) {
			return position.row == 0 
				|| antMap.isFilled(position.previousRow());
		}
	};
	public abstract void act(Position position);
	public abstract boolean shouldTurn(Position position, AntMap antMap);
	
	private static List<Action> list = new ArrayList<Action>();
	
	public static List<Action> actions() {
		if (!list.isEmpty()) return list;
		list.add(FORWARD);
		list.add(DOWN);
		list.add(BACKWARD);
		list.add(UP);
		return list;
	}
}

class Position {
	
	int row; 
	int col; 
	
	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}
	
	public Position previousCol() {
		return new Position(row, col-1);
	}
	public Position nextCol() {
		return new Position(row, col+1);
	}
	public Position previousRow() {
		return new Position(row-1, col);
	}
	public Position nextRow() {
		return new Position(row+1, col);
	}
}

class Ant {
	
	AntMap antMap = null;
	Action curentAction = Action.FORWARD;
	
	Ant(AntMap antMap) {
		this.antMap = antMap;
	}
	void crawl(Position position, int count) {
		antMap.matrix[position.row][position.col] = count;
		if (curentAction.shouldTurn(position, antMap))
			turn();
		curentAction.act(position);
	}

	private void turn() {
		List<Action> actions = Action.actions();
		curentAction = actions.get((actions.indexOf(curentAction)+1)%4);
	}
	
}

重复提交了。

看来有bug，firefox下提交一次完会报网络错误， resend就会出现重复提交的情况。

从来不知道Java的枚举可以这样用，岂不就像另一种泛型，只不过所有的具化类型全部预定义好了。
不过if-else多倒是真的，可以用取模和逻辑表达式代替。矩阵场景是我想多了，其实完全不影响算法流程。

最高效的办法是：直接先用数学方法总结出公式，然后直接用公式计算出任意行任意列的值。