矩阵中的路径（回溯法）

在该项目中 假设给定了下图中的二维数组，按照上述移动要求找到一个符合的数字序列
采用回溯法 ，首先给出目标序列的长度，定义一 个 长度计数单位（假定为 n） 每当按顺序找到了一个目标数字，n++ ，当n达到了目标序列的长度时，代表 已经 成功找到序列，返回成功

具体实现

首先需要找到入口点，即遍历整个数组 ，找到与序列第一个数字相同的位置，将这个位置传入find函数。
在find函数中 试图对 该位置的上下左右 （中没有被访问的位置） 进行查找 ，如果遇到在其上下左右 中发现了一个数字a 与目标序列中的第二位相同 ，即对该新发现的数字 进行上下左右的位置进行查找 ，直到完全查找结束，如果 a不能找到目标序列的第三位数字，那么对a进行回溯 ，将a置为 已访问 ，返回入口点 ，继续查找有没有 能够满足的 位置 ，依次推进

代码实现

寻找接入点 ：

for(int i=0;i<4;i++) {
			for(int j=0 ;j<4;j++) {
			
			if(findpath(isvistied,0,i,j,index,x)) {

判断是否到达目标序列的末尾

		if(pathlength==index.length) {
			System.out.println("x is  "+pathlength+"   index is "+index.length);
			System.out.println("i find it ");
			
			return true;
		}
		

寻找下一个目标序列

if(row >=0 && colunm >=0 && row < 4 && colunm < 4 && x[row][colunm]==index[pathlength] && !isvisited[row*4+colunm]) {
		 System.out.println("now row and colunm is "+  row+"   "+colunm);
		 System.out.println(x[row][colunm]);
		 pathlength++;
		 //设置已经被访问过 
		
		 isvisited[row*4+colunm]=true;
		 
		 //寻找下一个节点
		 haspath = findpath(isvisited,pathlength,row-1,colunm,index,x)||
				findpath(isvisited,pathlength,row+1,colunm,index,x)||
				findpath(isvisited,pathlength,row,colunm-1,index,x)||
				findpath(isvisited,pathlength,row,colunm+1,index,x)
				;
		
		
		 if(!haspath) {  //没有所需节点，需要回溯 
			 pathlength--;
			 isvisited[row*4+colunm]=false;
			 
		 }
		 
	 }

完整代码 ：

/**
 * 
 */

/***
 * @author 18071
 * @Date 2019年2月23日
 * 功能:  矩阵中的特定路径   
 * 1  2  3  4 
 * 5  6  7  8 //test 7
 * 9  10 11 12 
 * 13 14 15 16
 * 
 * 找到 2 6 7 11 15
 ***/


public class test {
	 static int [][] x=new int [][]
			  {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
	static int[] index= {2,6,7,11,15};
	
	public  static void main(String args[]) {
		
		if(haspath(x,index)) {
			System.out.println(haspath(x,index)+"w找到了给定序列");
		}
		else {
			System.out.println(haspath(x,index)+"  没有找到 该序列");
		}
		
	}
	
	//row 行 ，colunm 列 ,index 目标序列
	public static boolean haspath(int [][] x ,int [] index) {
		
		boolean emm=false;
		
		int pathlength=0;
		boolean isvistied[] =new  boolean [16];
		//false 默认为没有被访问过，
		//在遍历时，遍历没有被访问过的节点即可
		
		for(int i=0;i<isvistied.length;i++) {
			isvistied[i]=false;
			
		}
		
		//从第一个开始 
		for(int i=0;i<4;i++) {
			for(int j=0 ;j<4;j++) {
			
			if(findpath(isvistied,0,i,j,index,x)) {
				
				return true;
				
			}
			
			}
		}
		return emm;
		
		
	}
	
	public static boolean findpath(boolean[] isvisited, int pathlength,int row ,int colunm,int[]index ,int [][] x ) {
		
		boolean  haspath=false;
		
		
		
		
		if(pathlength==index.length) {
			System.out.println("x is  "+pathlength+"   index is "+index.length);
			System.out.println("i find it ");
			
			return true;
		}
		
		
		
		else if(row >=0 && colunm >=0 && row < 4 && colunm < 4 && x[row][colunm]==index[pathlength] && !isvisited[row*4+colunm]) {
		 System.out.println("now row and colunm is "+  row+"   "+colunm);
		 System.out.println(x[row][colunm]);
		 pathlength++;
		 //设置已经被访问过 
		
		 isvisited[row*4+colunm]=true;
		 
		 //寻找下一个节点
		 haspath = findpath(isvisited,pathlength,row-1,colunm,index,x)||
				findpath(isvisited,pathlength,row+1,colunm,index,x)||
				findpath(isvisited,pathlength,row,colunm-1,index,x)||
				findpath(isvisited,pathlength,row,colunm+1,index,x)
				;
		
		
		 if(!haspath) {  //没有所需节点，需要回溯 
			 pathlength--;
			 isvisited[row*4+colunm]=false;
			 
		 }
		 
	 }
		
		
	
		return haspath;
		
	}
}

*结果如下 *