Java实现深度搜索DFS算法详解

//回溯算法
flag[xx][yy]=1//标记
dfs(1,1,step+1)
//flag[xx][yy]=0;设置为未标记的点，进行回溯

    static int[] dx = {0, 1, 0, -1};//方向数组，顺时针：右 下 左 上
    static int[] dy = {1, 0, -1, 0};

 //试探墙壁，避免越界
        for(int i = 0; i <=6;i++){
           s[0][i]=1;
           s[i][0]=1;
           s[6][i]=1;
           s[i][6]=1;
        }

import java.util.Scanner;
public class test2 {

    static int[][] s = new int[10][10];
    static int[][] flag = new int[10][10];

    static int min = 99;//初始化认为该路径很大
    static int[] dx = {0, 1, 0, -1};//方向数组，顺时针：右 下 左 上
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //试探墙壁，避免越界
        for (int i = 0; i <= 6; i++) {
            s[0][i] = 1;
            s[i][0] = 1;
            s[6][i] = 1;
            s[i][6] = 1;
        }
        //将外围墙壁左上角顶点设置为（0，0）
        for (int i = 1; i < 6; i++)//这里的从1开始，省去外围墙壁带来的不便
        {
            for (int j = 1; j < 6; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        int sx = 1, sy = 1;//从（1，1）开始
        flag[sx][sy] = 1;//进行标记
        dfs(sx, sy, 0);//搜索
        if (min == 99)//如果值还是原来的，就说明不存在
            System.out.println("-1");
        else
            System.out.println(min);
    }

    public static void dfs(int x, int y, int step) {
        if (x == 5 && y == 5) {//到达了右下角，终点
            if (step < min) {//如果当前步数小于之前的
                min = step;//标记更新
            }
            return;//否则返回空
        }
        for (int i = 0; i < 4; i++) {//控制方向数组
            int xx = x + dx[i];//进行右，下，左，上搜索
            int yy = y + dy[i];
            if (flag[xx][yy] == 0 && s[xx][yy] == 0) {//如果未被标记，并且原来该位置的值为0
                flag[xx][yy] = 1;//标记
                dfs(xx, yy, step + 1);
                flag[xx][yy] = 0;//回溯
            }
        }

    }
}