蓝桥杯-迷宫问题(图)

迷南。 2022-04-12 13:57 202阅读 0赞

...11111111111111111111111111111  
11.111111........1111111111.1111  
11.111111..111.11111111.....1111  
11.11111111111.1111111111.111111  
11.111111.................111111  
11.111111.11111111111.11111.1111  
11.111111.11111111111.11111..111  
11..........111111111.11111.1111  
11111.111111111111111.11....1111  
11111.111111111111111.11.11.1111  
11111.111111111111111.11.11.1111  
111...111111111111111.11.11.1111  
111.11111111111111111....11.1111  
111.11111111111111111111111.1111  
111.1111.111111111111111......11  
111.1111.......111111111.1111.11  
111.1111.11111.111111111.1111.11  
111......11111.111111111.1111111  
11111111111111.111111111.111...1  
11111111111111...............1.1  
111111111111111111111111111111..

如上图的迷宫，入口，出口分别：左上角，右下角  
"1"是墙壁，"."是通路  
求最短需要走多少步？

测试数据1：  
21 32   
...11111111111111111111111111111  
11.111111........1111111111.1111  
11.111111..111.11111111.....1111  
11.11111111111.1111111111.111111  
11.111111.................111111  
11.111111.11111111111.11111.1111  
11.111111.11111111111.11111..111  
11.................11.11111.1111  
11111.111111111111.11.11....1111  
11111.111111111111.11.11.11.1111  
11111.111111111111.11.11.11.1111  
111...111111111111.11.11.11.1111  
111.11111111111111.11....11.1111  
111.11111111111111.11111111.1111  
111.1111.111111111.11111......11  
111.1111.......111.11111.1111.11  
111.1111.11111.111.11111.1111.11  
111......11111.111.11111.1111111  
11111111111111.111.11111.111...1  
11111111111111...............1.1  
111111111111111111111111111111..  
答案：53  
测试数据2：  
21 32  
...11111111111111111111111111111  
11.111111........1111111111.1111  
11.111111..111.11111111.....1111  
11.11111111111.1111111111.111111  
11.111111.................111111  
11.111111.11111111111.11111.1111  
11.111111.11111111111.11111..111  
11..........111111111.11111.1111  
11111.111111111111111.11....1111  
11111.111111111111111.11.11.1111  
11111.111111111111111.11.11.1111  
111...111111111111111.11.11.1111  
111.11111111111111111....11.1111  
111.11111111111111111111111.1111  
111.1111.111111111111111......11  
111.1111.......111111111.1111.11  
111.1111.11111.111111111.1111.11  
111......11111.111111111.1111111  
11111111111111.111111111.111...1  
11111111111111...............1.1  
111111111111111111111111111111..  
答案：61

##    DFS做法 ##

import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Scanner;
     
    public class Main {
    	
    	//行号
    	static int row ;
    	//列号
    	static int col ;
        public static void main(String[] args) throws FileNotFoundException { 
        	
        	
        	Scanner input = new Scanner(System.in);
        	//分割字符串，得到即将输入二维数组的行和列
        	//" +"是一个正则表达式，代表安装一个以上的空格进行分割
        	String[] ss = input.nextLine().trim().split(" +");
        	row = Integer.parseInt(ss[0]);
        	col = Integer.parseInt(ss[1]);;
        	
        	
        	
        	char[][] data = new char[row][col];
        	for(int i=0;i<row;i++){
        		data[i] = input.next().toCharArray();
        	}
        	
        	
        	
    		System.out.println(min_path(data,0,0));
    		
        }  
        
        public static int min_path(char[][] data,int x,int y){
        	//当走到最后一个位置 右下角的时候
        	//根据题目规定 我们是从 0,0出发的 
        	//假设 终点是 0,1  那么走到终点应该返回一个0
        	//代表只走一步就到达了终点
        	//可以理解成： 从 0，0 走到 0,0 只需要 0 步
        	if(x==row-1&&y==col-1){
        		return 0;
        	}
        	
        	//走到该位置 加上标记防止 往回走 
        	data[x][y] = '*';
        	
        	//现在走到终点的最小步数   初始值为Integer最大值 (-10 是为了 防止在+1后溢出)
        	int min = Integer.MAX_VALUE-10;
        	
        	//尝试向上走需要多少步。
    		if (x > 0 && data[x-1][y]=='.') {
    			//判断该向上走需要的步数是否是最小步数
    			min = Math.min(min, 1 + min_path(data, x - 1, y));
    		}
    		
    		//向下
    		if (x < row-1 && data[x+1][y]=='.') {
    			min = Math.min(min, 1 + min_path(data, x + 1, y));
    		}
    		
    		//向左
    		if (y > 0 && data[x][y-1]=='.'){
    			min = Math.min(min, 1 + min_path(data, x, y - 1));
    		}
    		
    		//向右
    		if (y < col-1 && data[x][y+1]=='.') {
    			min = Math.min(min, 1 + min_path(data, x, y + 1));
    		} 
    		
    		
    		//回溯在递归测试完毕找到所有最短路径后
    		//将该位置复原 (既然可以走到该位置，该位置肯定是.)
    		data[x][y] = '.';
    		
    		//如果，四个方向都没有走通，那么min还是初始值 Integer的最小值
    		//代表该位置作废 走不通
    		return min;
        }
     
        
    }

## 注意： ##

这个问题的解法在二维数组的"走动"类问题上适用性上具有很好的普遍性，在解法中，可以将向上，向下，向左，向右的逻辑算法同时列举， 但是这样看起来不简洁，可以使用一个小技巧，使用int\[\]\[\] d 来操作上下左右的移动，详见我的另一篇文章：

岛屿的数量：

[https://blog.csdn.net/qq\_35394891/article/details/84404156][https_blog.csdn.net_qq_35394891_article_details_84404156]

迷宫问题要比岛屿的数量问题稍简单

## BFS做法 ##

用本次的状态去派生出下次的状态，

直到有一次状态里有终点位置，说明找到了终点。

感觉比dfs快一点。

import java.util.*;
     
    public class A
    {
    	// from: 出发位置  goal: 目标位置
    	static int f(char[][] data, Set from, String goal){
    		if(from.contains(goal)) return 0; // 达到了最终的位置
    		
    		Set set = new HashSet(); // 找到from的相邻连通点
    		
    		for(Object obj: from){
    			String[] ss = ((String)obj).split(",");
    			int y = Integer.parseInt(ss[0]);
    			int x = Integer.parseInt(ss[1]);
    			
    			if(y>0 && data[y-1][x]=='.'){ data[y-1][x] = '*'; set.add(y-1+","+x); }
    			if(y<data.length-1 && data[y+1][x]=='.'){ data[y+1][x] = '*'; set.add(y+1+","+x); }
    			if(x>0 && data[y][x-1]=='.'){ data[y][x-1] = '*'; set.add(y+","+(x-1)); }
    			if(x<data[0].length-1 && data[y][x+1]=='.'){ data[y][x+1] = '*'; set.add(y+","+(x+1)); }
    		}
    		//没有找到任何后序可行的策略
    		if(set.isEmpty()) return -1;
    		int r = f(data, set, goal);
    		if(r<0) return -1;
    		return r + 1;
    	}
    	
    	public static void main(String[] args){
    		Scanner scan = new Scanner(System.in);
    		
    		String[] ss = scan.nextLine().trim().split(" +");
    		int n = Integer.parseInt(ss[0]);
    		int m = Integer.parseInt(ss[1]);
    		
    		char[][] data = new char[n][];
    		for(int i=0; i<n; i++){
    			data[i] = scan.nextLine().trim().toCharArray();
    		}
    		
    		Set set = new HashSet();
    		set.add("0,0");
    		System.out.println(f(data, set, n-1 + "," + (m-1)));
    	}
    }

[https_blog.csdn.net_qq_35394891_article_details_84404156]: https://blog.csdn.net/qq_35394891/article/details/84404156