【蓝桥杯】迷宫问题详解，辨析dfs和回溯

谁借莪１个温暖的怀抱￠ 2023-07-07 08:17 65阅读 0赞

> 定义一个二维数组：
> 
> int maze\[5\]\[5\] = \{
> 
> 0,1,0,0,0,
> 
> 0,1,0,1,0,
> 
> 0,0,0,0,0,
> 
> 0,1,1,1,0,
> 
> 0,0,0,1,0,
> 
> \}; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
> 
> 输入  
> 第一行: 整数m,n  
> 第二行: 整型二维数组  
> 输出 左上角到右下角的最短路径步数和路线，格式如样例所示。

输入  
5 5  
0 1 0 0 0  
0 1 0 1 0  
0 0 0 0 0  
0 1 1 1 0  
0 0 0 1 0  
输出  
8  
(0, 0)  
(1, 0)  
(2, 0)  
(2, 1)  
(2, 2)  
(2, 3)  
(2, 4)  
(3, 4)  
(4, 4)

## 辨析回溯法和深度优先搜索 ##

回溯法的步骤,在DFS的过程中发现不是问题的解，那么就开始回溯到上一层或者所以回溯法是DFS的一种应用，因为回溯法适用于问题的解空间是树的形式,DFS更像是一种工具  
以旅行售货员问题为例,当然迷宫问题的树是4叉的就需要用到for循环来做  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70]

回溯法框架

void DFS(int 当前状态)  
    {   
          if(当前状态为边界状态)  
          {   
            记录或输出  
            return;  
          }  
          for(i=0;i<n;i++)       //横向遍历解答树所有子节点 
          {   
               //扩展出一个子状态。 
               修改了全局变量  
               if(子状态满足约束条件和剪枝函数)  
                {   
                  dfs(子状态)  
               }  
                恢复全局变量//回溯部分 
          }  
    }

## 代码 ##

import java.util.Arrays;
    import java.util.Scanner;
    
    class Main { 
    	static int sx, sy, fx, fy, m, n, min = Integer.MAX_VALUE;/// 起始坐标,,结束坐标,矩阵长宽,最小步数阵
    	static int[][] a, track;// 矩阵,记录走过的位置
    	static int[] path, best;// 记录最佳的路线
    	static int[][] next = {  {  0, 1 }, {  1, 0 }, {  0, -1 }, {  -1, 0 } };// 右下左上的横纵坐标变化
    
    	public static void dfs(int x, int y, int step) { 
    		int tx = 0, ty = 0; // 下一步的坐标
    		if (x == fx && y == fy) { 
    			if (step < min) { 
    				min = step;
    				best = Arrays.copyOf(path, step);
    			}
    			return;
    		}
    		for (int i = 0; i < 4; i++) { 
    			tx = x + next[i][0];
    			ty = y + next[i][1];
    			if (tx < 0 || tx >= m || ty < 0 || ty >= n) { // 两个条件可以放在一起但是太长了
    				continue;
    			}
    			if (a[tx][ty] == 0 && track[tx][ty] == 0) { 
    				path[step] = i;
    				track[tx][ty] = 1;
    				dfs(tx, ty, step + 1);
    				track[tx][ty] = 0;
    			}
    		}
    		return;
    	}
    
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		m = sc.nextInt();
    		n = sc.nextInt();
    		a = new int[m][n];
    		track = new int[m][n];
    		path = new int[m * n];
    		best = new int[m * n];
    		for (int i = 0; i < m; i++) { 
    			for (int j = 0; j < n; j++) { 
    				a[i][j] = sc.nextInt();
    				track[i][j] = 0;
    			}
    		}
    		sx = sy = 0;
    		fx = m - 1;
    		fy = n - 1;
    		track[0][0] = 1;// 起始位置
    		dfs(sx, sy, 0);
    		System.out.println(min);
    		System.out.println("(" + sx + ", " + sy + ")");
    		for (int c = 0; c < min; c++) { 
    			sx = sx + next[best[c]][0];
    			sy = sy + next[best[c]][1];
    			System.out.println("(" + sx + ", " + sy + ")");
    		}
    		return;
    
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200221211207724.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2k2MjIzNjcx,size_16,color_FFFFFF,t_70