问题描述：
定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：
int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, };
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
提交代码
// 读入控制台的输入
while(num=readline()){
// 读取行列 m行 n列 num=num.split(' '); var m=num[0],n=num[1]; var maz=[]; // 存放二维数组 var path=[]; // 当前路径 var result=[] //最短路径 for(var i=0;i<m;i++){
// 读取到的数据存放到二维数组内 maz[i]=readline().split(' ').map((value)=>parseInt(value,10)) }
// 递归调用 find(0,0,path,result,maz,m,n)
// 打印结果 for(i=0;i<result.length;i++){ console.log('('+result[i][0]+','+result[i][1]+')') } }
function find(i,j,path,result,maz,m,n){
// 把当前的二维数组元素置为墙，表示已经走过，压入路径 maz[i][j]=1; path.push([i,j]);
// 当走到目标位置时，
// 假设结果为空或者结果的长度大于本次路径的长度，那么
// 本次路径的长度被保存到结果 if(i===m-1&&j===n-1){ if(result.length==0||result.length>path.length){ result.length=0;
// result.push(...path) } }
// 判断当前点的上下左右是不是可以走，如果可以走，递归调用 if(i-1>=0&&maz[i-1][j]===0){ find(i-1,j,path,result,maz,m,n) } if(i+1<m&&maz[i+1][j]===0){ find(i+1,j,path,result,maz,m,n) } if(j-1>=0&&maz[i][j-1]===0){ find(i,j-1,path,result,maz,m,n) } if(j+1<n&&maz[i][j+1]===0){ find(i,j+1,path,result,maz,m,n) }
// 置回状态 maz[i][j]=0;
// pop() 方法用于删除并返回数组的最后一个元素 path.pop(); }
回溯法概述：
回溯法（探索与回溯法）是一种优先搜索法，又称为试探法，按优先条件向前探索，以达到目标。但当探索到某一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
在回溯法中，每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解就通过在该集合中选择构造而成，这样的状态集合，其结构就是一颗多叉树。
回溯法解题
应用回溯法求解问题时，首先应明确定义问题的解空间，该解空间应至少包含问题的一个最优解。
在定义了问题的解空间，还需要将解空间有效地组织起来，使得回溯法方便的搜索整个解空间，通常将解空间组织成树或图的形式。
确定了问题的解空间结构后，回溯法将从开始结点（根节点）出发，以深度优先的方式搜索整个解空间。
开始结点成为活结点，同时也成为扩展结点，向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点，并成为当前的扩展结点。
如果在当前的扩展结点不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动（回溯）至最近的一个活结点，并使其称为当前的扩展结点。
回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或者解空间中已无活结点为止。
运用回溯法解题的三个关键
（1）针对给定的问题，定义问题的解空间
（2） 确定易于搜索的解空间结构
（3）以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效检索。
一般情况下可以用递归函数实现回溯法，递归函数模板如下：
void BackTrace(int t){ if(t>n){ Output(x) } else{ for(int i=f(n,t);i<=g(n,t);i++){ x[t] = h(i); if(Constraint(t)&&Bound(t)){ BackTrace(t+1); } } } }
t 表示递归深度，即当前扩展结点在解空间树中的深度；
n 用来控制递归深度，即解空间树的高度。
当 t>n时，算法已搜索到一个叶子结点，此时由函数Output(x)对得到的可行解x进行记录或输出处理。
用 f(n, t)和 g(n, t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号；
h(i)表示在当前扩展结点处x[t] 的第i个可选值；
函数 Constraint(t)和 Bound(t)分别表示当前扩展结点处的约束函数和限界函数。
若函数 Constraint(t)的返回值为真，则表示当前扩展结点处x[1:t] 的取值满足问题的约束条件；否则不满足问题的约束条件。若函数Bound(t)的返回值为真，则表示在当前扩展结点处x[1:t] 的取值尚未使目标函数越界，还需由BackTrace(t+1)对其相应的子树做进一步地搜索；否则，在当前扩展结点处x[1:t]的取值已使目标函数越界，可剪去相应的子树。