每日一题（小白）回溯篇4

深度优先搜索题：找到最长的路径，计算这样的路径有多少条（使用回溯）

分析题意可以得知，每次向前后左右走一步，直至走完16步就算一条走通路径。要求条件是不能超出4*4的范围，不能重复之前的路径。

①控制条件，若下一步已经被占有则返回

②控制条件，若下一步越界则返回

③控制条件，若下一步已到达末尾则返回，并且统计值+1

④若不在上述三个条件中则继续进行下一个点前后左右的试探，进去时需要将标记值设为1，出来后标记值为0

⑤主函数调用，将16个点每个都作为起点，调用回溯函数算出全部统计值

⑥输出统计值

代码如下👇

	static int[] dx= {0,1,0,-1};static int[] dy= {1,0,-1,0};static int[][] arr=new int[4][4];static int count=0;public static void main(String[] args) {for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {snack(i, j, 0);}}System.out.println(count);}//玩具蛇public static void snack(int x,int y,int len) {if (x>=4 || x<0 || y>=4 || y<0) {//先看有没有越界return;}if (arr[x][y]==1) {//下一步已经被占有return;}if (len>=15) {//走到结尾count ++;return;}for (int i = 0; i < 4; i++) {arr[x][y]=1;snack(x+dx[i], y+dy[i], len+1);arr[x][y]=0;//回溯精精髓}}

运行结果