对于迷宫问题的汇总总结

1查找出岛屿的数量

这一题需要思考在使用递归时是使用广度遍历还是深度遍历！我觉得这一题是在找的时候，是需要将所有的为1的值都要变成0，只要连起来都需要变成水。所以可以想象为从一个点出发，需要找到这个点周围所有的1，所以使用广度优先搜索！

class Solution {
    public int numIslands(char[][] grid) {
        //记录下当前岛屿的数量
        int m=grid.length;
        int n=grid[0].length;
        int result=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //说明是一个岛屿，需要进行 计数，然后将此岛屿周围为1的值都变成0；
                if(grid[i][j]=='1'){
                    result++;
                    solution(grid,i,j);
                }
            }
        }
        return result;
    }
    public void solution(char[][] map , int i,int j){
        //如果当前岛屿已经越界，或者直接为0，则可以直接返回
        if(i<0||i>=map.length||j<0||j>=map[0].length||map[i][j]=='0'){
            return ;
        }
        //走到此处，说明当前是一个岛屿，需要将该岛屿变成0
        map[i][j]='0';

        //然后向四个方向找岛屿，这里使用了广度优先搜索啊
        solution(map,i+1,j);
        solution(map,i-1,j);
        solution(map,i,j+1);
        solution(map,i,j-1);
    }
    
}

2迷宫只有一条路，并且一次走一步的问题输出路径(只有一条路径使用深度优先算法)

注意和第一题的区别！这题只是说找到一条路径即可，所以应该采用深度优先搜索的方式，当走不通之后，在进行回溯。

import java.util.*;
// 题目已经提示了 【迷宫只有一条通道】，则直接使用 DFS 找路径就行了，如有多条路径找最短考虑使用 BFS

public class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int rows=in.nextInt();
        int clos=in.nextInt();
        int[][] map = new int[rows][clos];
        for(int i=0;i<rows;i++){
            for(int j=0;j<clos;j++){
                map[i][j]=in.nextInt();
            }
        }
         List<Node> path= new ArrayList<>();

        backTracking(map,0,0,path);
        
        for(Node node: path){
            System.out.println("("+node.x+","+node.y+")");
        }
    }
    //使用深度优先搜索解决问题！
    public static boolean backTracking(int[][] map,int x,int y,List<Node> path){
        //怎么进行深度优先搜索进行查找呢？
        if(x==map.length-1&&y==map[0].length-1){
            path.add(new Node(x,y));
            return true;
        }
        //当前节点越界或者遇到墙，都不可以走
        if(x<0||x>map.length-1||y<0||y>map[0].length-1||map[x][y]==1){
            return false;
        }
        //当前节点可以继续走，所以需要将当前节点加入到路径中，并且置为已经走过
        path.add(new Node(x,y));
        map[x][y]=1;
         if(backTracking(map,x-1,y,path)){
            return true;
        }
        //向下走的通就向下走
        if(backTracking(map,x+1,y,path)){
            return true;
        }
       
        if(backTracking(map,x,y+1,path)){
           return true;
        }
        if(backTracking(map,x,y-1,path)){
             return true;
        }
        //此时都走不通，就直接返回,并且将走过的路置会去
        map[x][y]=0;
        path.remove(path.size()-1);
        return false;
        
        
    }
    
}
class Node{
    int x;
    int y;
    public Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}

3迷宫有多条路径，每次走一步，问最短的路径(因为有多条路径，所以需要广度优先搜索)

import java.util.*;

public class Main {
    public static ArrayList<int[]> path = new ArrayList<>();//搜索所有可能的路径
    public static ArrayList<int[]> best_path = new ArrayList<>();//最短路径
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            path.clear();
            best_path.clear();//每个用例之前，都要清空下路径
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] maze = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    maze[i][j] = in.nextInt();
                }
            }
            dfs(0,0,maze);//深搜+回溯
            for(int[] pathi:best_path){
                System.out.println("(" + pathi[0] + "," + pathi[1] + ")");
            }
        }
    }
    public static void dfs(int i,int j,int[][] maze){
        //越界了
        if(i<0 || i>maze.length-1 || j<0 || j>maze[0].length-1){
            return;
        }
        //撞墙了
        if(maze[i][j]==1){
            return;
        }
        //终止条件,找到终点了
        if(i==maze.length-1 && j==maze[0].length-1){
            path.add(new int[]{maze.length-1,maze[0].length-1});//添加终点
            if(best_path.size()==0 || path.size()<best_path.size()){//遇到更短的路径
                best_path.clear();//清空之前的路径
                for(int[] path0:path){
                    best_path.add(path0);
                }
            }
            return;
        }
        maze[i][j] = 1;//标记走过的点
        path.add(new int[]{i,j});//添加到路径中
        dfs(i-1,j,maze);
        dfs(i+1,j,maze);
        dfs(i,j-1,maze);
        dfs(i,j+1,maze);//以i j为中心，上下左右搜索
        maze[i][j] = 0;//回溯，恢复到之前的状态
        path.remove(path.size()-1);//回溯，移除最后一个点
    }
}

3迷宫有多条路径，每次最多走k步，问最少几步能走到？

（需要学习，暂时还没有解决，有好的解决办法记得踢我一脚。。。）