蛇形遍历数组
2011 年 1 月 18 日
蛇形遍历数组, 正常的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.
不过, 其实可以仅使用一个点坐标, 因为方向可以根据起点所在的边缘做出判断, 而起点就是上次的终点(再移一步). 另外, 需要把”两点连线”变成从一点出发, 向目标点行进”轨迹”. 所以, 并不需要3组变量(两个二维坐标和一个方向变量).
还有一个思维上的坑, 那就是在分析时, 转折线(草稿纸上)会造成干扰, 其实只需要画斜线即可, 并没有所谓的转折线. 这是用连续(Anolog)来分析离散时容易出现的干扰.
如果没有经过同类训练, 我怀疑能否快速地将3组变量优化成1组变量. 类似解数学题过程中的所谓的”关键点”, 这些关键点往往是无法通过逻辑来推导的, 更多是一种经验, 或者穷举得出的结果.
回到这个问题, 我觉得采用分而治之的方法 – 即把问题归纳分解成:
不过, 其实可以仅使用一个点坐标, 因为方向可以根据起点所在的边缘做出判断, 而起点就是上次的终点(再移一步). 另外, 需要把”两点连线”变成从一点出发, 向目标点行进”轨迹”. 所以, 并不需要3组变量(两个二维坐标和一个方向变量).
还有一个思维上的坑, 那就是在分析时, 转折线(草稿纸上)会造成干扰, 其实只需要画斜线即可, 并没有所谓的转折线. 这是用连续(Anolog)来分析离散时容易出现的干扰.
如果没有经过同类训练, 我怀疑能否快速地将3组变量优化成1组变量. 类似解数学题过程中的所谓的”关键点”, 这些关键点往往是无法通过逻辑来推导的, 更多是一种经验, 或者穷举得出的结果.
回到这个问题, 我觉得采用分而治之的方法 – 即把问题归纳分解成:
* 移动点(几乎都会认为是两个点而不是一个点)
* 两点连线(两个点只能通过上一步来判断方向, 最终还是决定引入方向变量)
就几乎很难得出最优的方案, 我在搜索引擎上查到几乎所有采用此种分析问题方法的人, 都会陷入大量的状态判断.
void print_spiral(int m , int n){ vector> matrix(m); for(int i=0; i (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"); } }