当前位置: 首页 > article >正文

老鼠迷宫,汉诺塔,八皇后,回溯算法案例

  1. 老鼠迷宫
    public class MiGong{
    	public static void main(String[] args) {
    		//用二维数组表示墙,用1表示,8行7列
    		int arr[][] = new int[8][7];
    
    		
    		for(int i=0;i<8;i++){
    			for(int j=0;j<7;j++){
    				arr[i][j]= 0;
    			}
    		}
    				
    	
    		//第一行,第8行都设为1.
    		for(int i=0;i<8;i++){
    			if(i==0||i==7){
    				for(int j=0;j<7;j++){
    					arr[i][j] = 1;
    					
    				}
    			}
    			System.out.println();
    		}
    		//第一列,第7列都设为1
    		for(int j=0;j<7;j++){
    			if(j==0||j==6){
    				for(int i=0;i<8;i++){
    					arr[i][j]=1;
    				}
    			}
    		}
    		arr[3][2] = 1;
    		arr[2][2] = 1;
    		arr[3][1] = 1;
    
    
    		//创建对象
    		T mouse = new T();
    		mouse.findway(arr,1,1);
    
    
    
    		for(int i=0;i<8;i++){
    			for(int j=0;j<7;j++){
    				System.out.print(arr[i][j]+" ");
    			}
    			System.out.println();
    		}
    		
    		
    	}
    }
    
    class T{
    	//使用递归回溯的思想。
    	//1.创建一个findway方法找出迷宫路径
    	//2.找到返回true,没找到返回false
    	//3.arr就是二维数组,表示迷宫
    	//4.i,j是老鼠的位置,初始化为[1][1]
    	//5。规定二维数组各个值的含义,
    	//0 表示可以走,1 表示障碍物,2 表示可以走,3 表示走过但是走不通的思路
    	//6.当arr[6][5] = 2就说明找到通路,就可以结束,否则就继续找。
    	//找路策略 下--》右--》上--》左。
    	public boolean findway(int arr[][],int i,int j){
    		
    		if(arr[6][5]==2){
    			return true;
    		}else{
    			
    			if(arr[i][j]==0){//说明可以走
    				arr[i][j] = 2;//假定这个位置可以走通。
    				//找路策略 下--》右--》上--》左。
    				if(findway(arr,i+1,j)){
    					return true;
    				}else if(findway(arr,i,j+1)){
    					return true;
    				}else if(findway(arr,i-1,j)){
    					return true;
    				}else if(findway(arr,i,j-1)){
    					return true;
    				}else{
    					arr[i][j] = 3;
    					return false;
    				}
    			}else{ //arr[i][j] = 1,2,3;
    				return false;
    			}
    		}
    	}
    
    
    
    
    
    
    
    
    
    }
    
    
    
    

  2. 汉诺塔,记住思路
    public class HanoiTower{
    	public static void main(String[] args) {
    		T tower = new T();
    		tower.move(3,'A','B','C');
    		
    	}
    }
    
    class T{
    	//方法
    	//num 表示移动的个数,a,b,c分别表示A塔,B塔,C塔
    	public void move(int num,char a,char b,char c){
    		//如果只有一个盘num=1
    		if(num == 1){
    			System.out.println(a + "->"+ c);
    		}else{
    			//如果有多个盘,可以看成两个,最下面的和最上面的所有盘(num-1)
    			//1.先移动上面所有盘到b,借助c
    			move(num-1,a,c,b);
    			//2.把最下面的这个盘,移动到c
    			System.out.println(a+"->"+c);
    			//3.再把b塔的所有盘,移动到c,借助a
    			move(num-1,b,a,c);
    		}
    	}
    }

  3. 八皇后没做出来,哈哈哈

http://www.kler.cn/a/5696.html

相关文章:

  • Log4j2的RollingFileAppender详解
  • linux系统编程(3)--系统调用
  • 文章八:YOLOv5车牌识别系统的Web应用与API开发
  • Java设计模式(二十一)—— 外观模式
  • 歌德巴赫猜想数学证明
  • Leetcode.2171 拿出最少数目的魔法豆
  • element plus 语言切换组件使用
  • python——面向对象(下)
  • C 中的循环
  • Jenkins使用
  • 【计算机视觉 | 目标检测】DETR风格的目标检测框架解读
  • QT之QCamera
  • Java多态
  • 阶乘约数——蓝桥杯python组国赛题(C++、唯一分解定理)
  • 利用 Docker 搭建主从服务器
  • Spring MVC 之 ViewResolver
  • 索马里ECTN/BESC/CTN证书
  • 【新2023Q2押题JAVA】华为OD机试 - 服务依赖
  • 启动优化小结
  • UDSonLIN(ISO14229-7)诊断协议