1.迷宫

A组和C组果然不一样，填空第一签到题就开了dfs
image.png
image.png

1.1思路分析

迷宫问题，但是题主本人并没有做过类似的题目，知道以dfs的方法解题，但是思路想错了：dfs递归遍历二维数组，将当前格子记为已标记，如果当前格子四周有一个地方能走出迷宫，那么就把当前格子设置为通路，那么其他任何地方只要能走到这个位置的人都能走出迷宫，这个思路和岛屿问题很像，但是我并没有考虑走过的格子是标记过的，标记的格子走到了会自动退出循环，所以导致我后面没能成功AC（也可能是本人太菜了）。

  • 正确思路：

从上面的图中可以知道，如果当前的格子是不能走出迷宫的，那么最后必然会走进已经走过的格子，根绝这个思路，我们确定dfs的思路，如果递归结果已经走出了迷宫之外，那么表示当前的人能够走出迷宫，则count++。并且把每次经过的地方都标记已经走过（这里需要注意的是，我们的vis数组在每次dfs的时候都需要初始化，因为不同的人——即不同的入口都是不相关的），相反的如果当前的入口最后会走入一个已经走过的格子的话，直接退出当前的dfs。

1.2代码

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  4. public class Main2 {
  5.     static int count=0;
  6.     static boolean[][] vis=new boolean[10][10];
  7.     //static boolean[][] can=new boolean[10][10];
  8.     public static void main(String[] args) {
  9.         char[][] arr=new char[10][10];
  10.         Scanner sc=new Scanner(System.in);
  11.         for(int i=0;i<arr.length;i++){
  12.             String s=sc.nextLine();
  13.             for(int j=0;j<arr[i].length;j++){
  14.                 arr[i][j]=s.charAt(j);
  15.             }
  16.         }
  17. //        for (int i = 0; i < arr.length; i++) {
  18. //            for(int j=0;j<arr[i].length;j++){
  19. //                System.out.print(arr[i][j]);
  20. //            }
  21. //            System.out.println();
  22. //        }        //打印迷宫
  23.         for(int i=0;i<arr.length;i++){
  24.             for(int j=0;j<arr[i].length;j++){
  25.                 for(int k=0;k<vis.length;k++){
  26.                     Arrays.fill(vis[k],false);    //初始化数组
  27.                 }
  28.                 dfs(arr,i,j);
  29.             }
  30.         }
  31.         System.out.println(count);
  33.     }
  34.     public static void dfs(char[][] arr,int i,int j){
  35.         if(i<0||i>=arr.length||j<0||j>=arr[i].length){
  36.             count++;
  37.             return;
  38.         }
  39.         if(vis[i][j]){
  40.             return;
  41.         }
  42.         vis[i][j]=true;
  43.         if(arr[i][j]=='U')dfs(arr,i-1,j);
  44.         if(arr[i][j]=='D')dfs(arr,i+1,j);
  45.         if(arr[i][j]=='L')dfs(arr,i,j-1);
  46.         if(arr[i][j]=='R')dfs(arr,i,j+1);
  47.     }
  48. }