蛇形遍历数组

蛇形遍历数组, 正常的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.

不过, 其实可以仅使用一个点坐标, 因为方向可以根据起点所在的边缘做出判断, 而起点就是上次的终点(再移一步). 另外, 需要把"两点连线"变成从一点出发, 向目标点行进"轨迹". 所以, 并不需要3组变量(两个二维坐标和一个方向变量).

还有一个思维上的坑, 那就是在分析时, 转折线(草稿纸上)会造成干扰, 其实只需要画斜线即可, 并没有所谓的转折线. 这是用连续(Anolog)来分析离散时容易出现的干扰.

如果没有经过同类训练, 我怀疑能否快速地将3组变量优化成1组变量. 类似解数学题过程中的所谓的"关键点", 这些关键点往往是无法通过逻辑来推导的, 更多是一种经验, 或者穷举得出的结果.

回到这个问题, 我觉得采用分而治之的方法 - 即把问题归纳分解成:

* 移动点(几乎都会认为是两个点而不是一个点)

* 两点连线(两个点只能通过上一步来判断方向, 最终还是决定引入方向变量)

就几乎很难得出最优的方案, 我在搜索引擎上查到几乎所有采用此种分析问题方法的人, 都会陷入大量的状态判断.

void print_spiral(int m , int n){
	vector<vector<int>> matrix(m);
	for(int i=0; i<m; i++){
		matrix[i] = vector<int>(n);
	}
	
	int num = 1;
	matrix[0][0] = num++;
	int i=0;
	int j=0;
	while(1){
		if(i == m-1 && j == n-1){
			break;
		}
	
		if(i == 0 || j == n-1){
			j++;
			if(j >= n){
				j --;
				i ++;
			}
			while(1){
				matrix[i][j] = num++;
				if(j == 0 || i == m-1){
					break;
				}
				i++;
				j--;
			}
		}else{
			i++;
			if(i >= m){
				i --;
				j ++;
			}
			while(1){
				matrix[i][j] = num++;
				if(i == 0 || j == n-1){
					break;
				}
				i--;
				j++;
			}
		}
	

	}
	
	for(auto r : matrix){
		for(auto c : r){
			printf("%d ", c);
		}
		printf("\n");
	}
}