Java数据结构与算法——递归篇

た入场券 2023-10-04 07:16 56阅读 0赞

> Java数据结构与算法: [https://blog.csdn.net/weixin\_46822367/article/details/115478461?spm=1001.2014.3001.5502][https_blog.csdn.net_weixin_46822367_article_details_115478461_spm_1001.2014.3001.5502].  
> 
> 
> #### 目录 ####
> 
>  *   *   *  1、==迷宫回溯==
>          *  2、==八皇后==

#### 1、迷宫回溯 ####

package com.lyp.recursion;
    
    public class MiGong {
        
    
    	public static void main(String[] args) {
        
    		//先创建二维数组，模拟迷宫
    		//地图
    		int[][] map = new int[8][7];
    		//使用1表示墙
    		//上下全部置为1
    		for(int i = 0; i < 7; i++) {
        
    			map[0][i] = 1;
    			map[7][i] = 1;
    		}
    		//左右全部置为1
    		for(int i = 0; i < 8; i++) {
        
    			map[i][0] = 1;
    			map[i][6] = 1;
    		}
    		//设置挡板，1表示
    		map[3][1] = 1;
    		map[3][2] = 1;
    		//输出地图
    		System.out.println("地图的情况");
    		for(int i = 0; i < 8; i++) {
        
    			for(int j = 0; j < 7; j++) {
        
    				System.out.printf(map[i][j]+" ");
    			}
    			System.out.println();
    		}
    		
    		//使用递归回溯给小球找路
    		//setWay(map,1,1);
    		setWay2(map,1,1);
    		
    		//输出新的地图，小球走过，并标识过的地图
    		System.out.println("小球走过，并标识过的地图的情况");
    		for(int i = 0; i < 8; i++) {
        
    			for(int j = 0; j < 7; j++) {
        
    				System.out.printf(map[i][j]+" ");
    			}
    			System.out.println();
    		}
    	}
    
    	//使用递归回溯来给小球找路
    	//说明
    	//1.map 表示地图
    	//2. i,j 表示从地图的哪个位置开始出发(1,1)
    	//3. 如果小球能 到 map [6][5] 位置，则说明通路找到
    	//4.约定： 当map[i][j] 为 0 表示该点没有走过 当为1表示墙 ；2 表示通路可以走 ；3 表示已经走过，但是走不通
    	//5.在走迷宫时，需要确定一个策略（方法） 下->右->上->左，如果该点走不通再回溯
    	
    	/**
    	 * 
    	 * @param map 表示地图
    	 * @param i 从哪个位置开始的
    	 * @param j
    	 * @return 如果找到通路,就返回true，否则返回false
    	 */
    	public static boolean setWay(int[][] map ,int i, int j) {
        
    		if(map[6][5] == 2) {
        //通路已经找到
    			return true;
    		} else {
        
    			if(map[i][j] == 0) {
        //如果当前这个点还没有走过
    				//按照策略  下->右->上->左 走
    				map[i][j] = 2; //假定该点可以走通
    				if(setWay(map,i+1,j)) {
        //向下走
    					return true;
    				} else if(setWay(map,i,j+1)) {
        //向右走
    					return true;
    				} else if(setWay(map,i-1,j)) {
        //向上走
    					return true;
    				} else if(setWay(map,i,j-1)) {
        //向左走
    					return true;
    				} else {
        
    					//说明该点是走不通的，是死路
    					map[i][j] = 3;
    					return false;
    				} 
    			} else {
         //如果map[i][j] != 0 ,可能是 1,2,3
    				return false;
    			}
    		}
    		
    	}
    	
    	//修改找路的策略 改为 上->右->下->左
    	public static boolean setWay2(int[][] map ,int i, int j) {
        
    		if(map[6][5] == 2) {
        //通路已经找到
    			return true;
    		} else {
        
    			if(map[i][j] == 0) {
        //如果当前这个点还没有走过
    				//按照策略  上->右->下->左 走
    				map[i][j] = 2; //假定该点可以走通
    				if(setWay2(map,i-1,j)) {
        //向上走
    					return true;
    				} else if(setWay2(map,i,j+1)) {
        //向右走
    					return true;
    				} else if(setWay2(map,i+1,j)) {
        //向下走
    					return true;
    				} else if(setWay2(map,i,j-1)) {
        //向左走
    					return true;
    				} else {
        
    					//说明该点是走不通的，是死路
    					map[i][j] = 3;
    					return false;
    				} 
    			} else {
         //如果map[i][j] != 0 ,可能是 1,2,3
    				return false;
    			}
    		}
    		
    	}
    }

#### 2、八皇后 ####

package com.lyp.recursion;
    
    public class Queue8 {
        
    	
    	//定义一个max表示共有多少个皇后
    	int max = 8;
    	//定义一个数组 Array,保存皇后放置的位置的结果,如 arr = {0,4,7,5,2,6,1,3}
    	int[] array = new int[max];
    	static int count = 0;
    	static int judgeCount = 0;
    	public static void main(String[] args) {
        
    		//测试一把
    		Queue8 queue8 = new Queue8();
    		queue8.check(0);
    		System.out.printf("一共有%d种解法",count);
    		System.out.printf("一共判断冲突的%d次",judgeCount);
    	}
    
    	//编写一个方法，放置第n个皇后
    	//特别注意：check 是每一次递归是，进入check都有 一次 for(int i = 0; i < max; i++)，因此会有回溯
    	private void check(int n) {
        
    		if(n == max) {
        //n = 8,其实8个皇后已经被放好
    			print();
    			return;
    		}
    		
    		//依次放入皇后,并判断是否冲突
    		for(int i = 0; i < max; i++) {
        
    			//先把当前这个皇后n,放到这行的 第1列
    			array[n] = i;
    			//判断当放置第n个皇后到i列时，是否冲突
    			if(judge(n)) {
        //不冲突
    				//接着放n+1个皇后，即开始递归
    				check(n+1);
    			}
    			//如果冲突，就继续执行 array[n] = i;	即将第n个皇后放置在本行的后一个位置
    		}
    	}
    	
    	//查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
    	/**
    	 * 
    	 * @param n 表示第 n 个皇后
    	 * @return
    	 */
    	private boolean judge(int n) {
        
    		judgeCount++;
    		for(int i = 0; i < n; i++) {
        
    			//说明
    			//1.array[i] == array[n] 表示判断 第n 个皇后是否和前面的n-1个皇后在同一列
    			//2.Math.abs(n-i) == Math.abs(array[n] - array[i] 表示判断第n个皇后是否和第i个皇后是否在同一斜线
    			//n =1 放置第二列  n=1 array[1] = 1
    			//Math.ads(1-0) == 1 Math.abs(array[n] -array[i]) = Math.abs(1-0) = 1
    			//3. 判断是否在同一列 ，没有必要，n每次都在递增
    			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])) {
        
    				return false;
    			}
    		}
    		return true;
    	}
    	
    	//写一个方法，可以将皇后摆放的位置输出
    	private void print() {
        
    		count++;
    		for (int i = 0; i < array.length; i++) {
        
    			System.out.printf(array[i] + " ");
    		}	
    		System.out.println();
    	}
    	
    }

[https_blog.csdn.net_weixin_46822367_article_details_115478461_spm_1001.2014.3001.5502]: https://blog.csdn.net/weixin_46822367/article/details/115478461?spm=1001.2014.3001.5502