王道论坛机试指南学习笔记（五）搜索

1. 枚举

- 简述

• 尝试搜索空间内所有可能的解
• 搜索空间越大，使用枚举进行搜索的复杂度就越高

- 百鸡问题

• 题目：用小于等于 n 元去买 100 只鸡，大鸡 5 元/只，小鸡 3 元/只,还有 1/3 元每只的一种小鸡，分别记为 x 只,y 只,z 只。编程求解 x,y,z 所有可能解。

• 解决方式：暴力枚举

• 方法：

  public static void HundredChicks(int sum){
    for (int i = 0; i <= 100; i++) {
      for (int j = 0; j <= 100-i; j++) {
        int z = 100 -i -j;
        // 采用对不等式两端所有数字都乘3的操作，避免除法带来的精度损失
        if(i*5*3+j*3*3+z < sum*3)
          System.out.println("x="+i+", y="+j+", z="+z);
      }
    }
  }
  

• 总结：在复杂度允许的范围内，直白的枚举思路简单，代码清晰，所以在一些看似无从下手的题目面前，我们要换个角度，试着从更暴力的角度去思考

2.2 BFS

- 算法

• 问题的解空间内有若干可能的状态，每一次状态迁移都从这些可能状态中选择一个执行；

• 包含搜索空间中所有状态的树：解答树

  • 所谓广度优先搜索，即在遍历解答树时使每次状态转移时扩展出尽可能多的新状态，并且按照各个状态出现的先后顺序依次扩展它们。
    

• 剪枝：

  • 剪去解答树中不可能是我们所需答案的子树，减少所有范围，提高搜索效率；

• 使用队列实现:

  • 将每次扩展得到的新状态放入队列中；
  • 只有排在该状态之前的所有状态都被扩展完成，才对此状态进行扩展；

• 使用标记数组：

  • 为防止对无效状态的重复搜索，增加标记数组；
  • 当已经访问过一个状态后，将其状态在标记数组中对应的位置进行标记（true/false）

- 迷宫问题

• 题目简述：

Ignatius 被魔王抓走了,有一天魔王出差去了,这可是 Ignatius 逃亡的好机会. 魔王住在一个城堡里,城堡是一个 ABC 的立方体,可以被表示成 A 个 B*C 的矩 阵,刚开始 Ignatius 被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现 在知道魔王将在 T 分钟后回到城堡,Ignatius 每分钟能从一个坐标走到相邻的六个 坐标中的其中一个.现在给你城堡的地图,请你计算出 Ignatius 能否在魔王回来前 离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃 亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1。

• 三维迷宫，从 {0,0,0} 出发，到达对角线出口即为胜利；
• 迷宫中 1 表示墙，0 表示路；

static boolean[][][] mark;
static int[][][] maze = {{{0,1,1,1}, {0,0,1,1}, {0,1,1,1}}, {{1,1,1,1}, {1,0,0,1}, {0,1,1,1}}, {{0,0,0,0}, {0,1,1,0}, {0,1,1,0}}};
static int[][] options = {{1,0,0}, {-1,0,0}, {0,1,0}, {0,-1,0}, {0,0,1}, {0,0,-1}};
static Queue<Cell> queue = new LinkedList<>();

static int BFS(int a, int b, int c){
    while (!queue.isEmpty()){
        Cell cell = queue.poll();
        int x = cell.x, y = cell.y, z = cell.z;
        for (int i = 0; i < options.length; i++) {
            x = cell.x + options[i][0];
            y = cell.y + options[i][1];
            z = cell.z + options[i][2];
            //排除特殊情况，当前前进目标不在迷宫内、当前位置已访问或当前位置是墙，则跳过该位置
            if ( x<0 || x>a-1 || y<0 || y>b-1 || z<0 || z>c-1) continue;
            if (mark[x][y][z]) continue;
            if (maze[x][y][z]==1) continue;
            Cell new_cell = new Cell(x, y, z, cell.time+1);
            queue.offer(new_cell);
            mark[x][y][z] = true;
            if(x==a-1&&y==b-1&&z==c-1) return new_cell.time;
        }
    }
    return -1;
}

- 可乐问题

• 问题描述：

大家一定觉得运动以后喝可乐是一件很惬意的事情，但是 seeyou 却不这么 认为。因为每次当 seeyou 买了可乐以后，阿牛就要求和 seeyou 一起分享这一瓶可乐，而且一定要喝的和 seeyou 一样多。但 seeyou 的手中只有两个杯子，它们的容量分别是 N 毫升和 M 毫升可乐的体积为 S (S<101)毫升(正好装满一 瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101>S >0，N>0，M>0) 。聪明的 ACMER 你们说他们能平分吗?如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

• 问题简述：

  • 三个没有刻度的杯子相互倒可乐，直到达到有两个杯子中的可乐体积相同（平分）；

  • 初始条件下，A杯盛满可乐，A杯容量=B杯容量+C杯容量。

  （吐槽一下，王道描述题目的能力实在需要提高…读三遍题目都没怎么理解题意 又看两遍C++代码才搞懂…）

• 解决思路：

  • 关键在于，将此问题抽象为广度优先搜索的过程，将三个杯中盛有不同体积的可乐视为一种可行的状态，即迷宫中的每个格子；
  • 由于可乐总体积不变，所以会有根本无法到达的格子，但在本问题中，由于限制了每次状态改变函数的逻辑，因此不考虑这些不可达格子的情况；
  • 每次循环有六种可能的状态改变：
    • 从A杯向B杯倾倒；
    • 从B杯向A杯倾倒；
    • 从A杯向C杯倾倒；
    • 从C杯向A杯倾倒；
    • 从B杯向C杯倾倒；
    • 从C杯向B杯倾倒。
  • 在每次状态改变时，记录到达当前状态时需要倾倒的次数，也就是可能的结果；
  • 若到达某个状态，使得当前状态下，某两个杯子中的可乐体积都为总体积的一半，则根据BFS的特性，找到最短倾倒次数，解决问题。

• 实现代码：

  /**
       * 倾倒函数，从容量为a的杯向容量为b的杯倒可乐
       * @param a a杯容量
       * @param ca a杯当前可乐体积
       * @param b b杯容量
       * @param cb b杯当前可乐体积
       */
  private static int[] Pour(int a, int ca, int b, int cb){
    //a中可乐可以全部倒入b杯
    if((b-cb)>ca){
      cb += ca;
      ca = 0;
    }
    else {
      ca -= (b-cb);
      cb = b;
    }
    return new int[]{ca, cb};
  }
  
  /**
       * 检查当前状态是否得到平分
       * @param a a杯当前容量
       * @param b b杯当前容量
       * @param c c杯当前容量
       * @param s 可乐总体积
       * @param time 得到当前状态的倾倒次数
       * @return
       */
  private static boolean CheckResult(int a, int b, int c, int s, int time){
    // 如果没有到达过当前状态，则存储，否则跳过
    if(!mark[a][b][c]){
      mark[a][b][c] = true;
      Cell new_cell = new Cell(a, b, c, time);
      // 若实现平分，结束BFS，返回当前倾倒次数
      if((a==s/2&&b==s/2)||(a==s/2&&c==s/2)||(c==s/2&&b==s/2))
        return true;
      // 若未平分，将当前新状态放入队列，继续进行搜索
      queue.offer(new_cell);
    }
    return false;
  }
  
  /**
       * 非常可乐题目，三种容量的容器，一定量可乐，求倒几次能实现平分
       * @param s 可乐的体积
       * @param n a杯体积
       * @param m b杯体积
       * @return 返回到达平分需要的步数，如果不能到达，返回-1
       */
  static int PourCola(int s, int n, int m){
    while (!queue.isEmpty()){
      Cell cell = queue.poll();
  
      // a倒向b
      int a = cell.x, b = cell.y, c = cell.z;
      int[] result = Pour(s, a, n, b);
      a = result[0]; b = result[1];
      if(CheckResult(a, b, c, s, cell.time+1))
        return cell.time+1;
      
      // 中间4种条件略
  
      // c倒向a
      a = cell.x; b = cell.y; c = cell.z;
      result = Pour(m, c, s, a);
      a = result[1]; c = result[0];
      if(CheckResult(a, b, c, s, cell.time+1))
        return cell.time+1;
    }
    return -1;
  }
  

- 解题关键

• 使用BFS解决问题有三个关键：
  1. 确定状态，通过状态的转移来进行广度优先搜索（状态可以理解为迷宫问题中的每个格子）；
  2. 确定状态的扩展方式，也就是在每个状态下，通过何种方式能够到达其他状态，需要找到这样的通用方法（扩展方式可以理解为，迷宫问题中人物的6个走向）；
  3. 最优解，要找到问题中所要达到的“最优”状态，如迷宫问题中的最少步数、可乐问题中的最少倾倒次数，当问题中出现上述有关“最优”的关键字，则可以考虑使用BFS来解决。

3. 递归

- 思想

• 让函数调用自己本身，但必须设定递归的出口（达到某种条件，停止递归）
• 两个要素：
  • 递归方式：通过何种规律，让函数循环计算下去
  • 递归出口：达到何种条件，能够停止计算

- 汉诺塔

• 题目描述

约 19 世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆， 最左边的杆上自上而下、由小到大顺序串着由 64 个圆盘构成的塔。目的是将最 左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘 放在小盘的上面。现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右 (左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上 面。Daisy 已经做过原来的汉诺塔问题和汉诺塔 II，但碰到这个问题时，她想了 很久都不能解决，现在请你帮助她。现在有 N 个圆盘，她至少多少次移动才能 把这些圆盘从最左边移到最右边?

• 解题思路：

  • 首先考虑基本汉诺塔问题，将 x 个圆盘从 A 柱移动到 B/C 柱，相当于先将其上面的 x-1 个圆盘从 A 柱移动到 C/B 柱，然后将最下面的大圆盘移动到 B/C 柱，最后再将上面的 x-1 个圆盘从 A 柱移动到 B/C 柱，因此可以很容易求出，递归表达式为：F(x) = 2*F(x-1) + 1；
  • 由此推理，分析本题。题目中要求圆盘只能通过中间 B 柱移动，不能直接从 A 到 C 或从 C 到 A，因此同样的推理，将 x 个圆盘从 A 柱移动到 C 柱所需步骤为：
    • 将上面 x-1 个圆盘从 A 柱通过 B 柱移动到 C 柱：F( x-1 )
    • 将最下面的大圆盘从 A 柱移动到 B 柱：1
    • 将 x-1 个圆盘从 C 柱通过 B 柱移动回 A 柱：F( x-1 )
    • 将下面大圆盘从 B 柱移动到 C 柱：1
    • 将 x-1 个圆盘从 A 柱通过 B 柱再移动到 C 柱：F( x-1 )
  • 从而得出，本题的递归表达式为：F(x) = 3*F(x-1) + 2。

• 代码：

  //汉诺塔递归函数
  private static int Hannoid(int x){
    if(x==1) return 1;
    return 1+2*Hannoid(x-1);
  }
  //汉诺塔III递归函数
  private static int HannoidIII(int x){
    if(x==1) return 2;
    return 2+3*HannoidIII(x-1);
  }
  

- 素数环问题

• 题目描述

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.

• 问题简述：

  • 把 n 个自然数填到一个环中，使得环上任意相邻两数之和为素数
  • 题目条件：1 < n < 17

• 解题思路：

  • 首先考虑使用回溯法解决问题，依次填充【尚未加入素数环的自然数】，判断是否依然构成素数环：若该数与相邻自然数之和仍为素数，则继续递归；若和不是素数，则回溯，替换数字，直到找到所有可能的解并打印；
  • 代码逻辑:
    • 首先根据题意，n 的范围在 1~17 之间， 2~31 之间的素数，设置此数组，用于判断素数和；
    • 其次，需要一个布尔值数组，存储每个自然数是否已经被添加到结果集中（已添加则为true）；
    • 创建递归函数，设置两个结束条件:
      1. 结果集的后两个自然数之和不是素数，结束递归，进行回溯；
      2. 结果集已满，判断是否成素数环，若不是则回溯，否则打印当前结果。
    • 递归函数中的循环：
      • 每次从自然数组中找到一个未被使用过的数，加入结果集；
      • 使用新的结果集进行递归，判断是否达到临界条件；
      • 若回溯，则将该数标记为 false，用于后面继续递归。

• 代码：

  // 素数环问题中的素数数组，因为 1<n<17，所以素数和最大为 15+16=31
  private static int[] prime = {2,3,5,7,11,13,17,19,23,29,31};
  private static int[] result = new int[17];
  private static boolean[] marked = new boolean[17];
  
  // 素数环问题中，判断一个数是否为素数
  private static boolean IsNotPrime(int n){
    for (int p:prime)
      if(p==n) return false;
    return true;
  }
  
  /**
   * 素数环问题，把 n 个自然数填到一个环中，使得环上任意相邻两数之和为素数
   * 打印可能的顺时针、逆时针结果
   * @param n 自然数的个数
  */
  private static void PrimeRing(int sum, int n){
    // 结果集中有两个及以上自然数，检查最后两个之和是否为素数
    if(n > 0) 
      if (IsNotPrime(result[n] + result[n - 1])) return;
    
    // 当前结果集已经放入 n 个数，检查最后一对自然数之和并输出结果
    if(n == sum-1){
      if(IsNotPrime(result[n]+result[0])) return;
      System.out.print("Answer is: ");
      for (int i = 0; i <= n; i++) {
        System.out.print(result[i]);
        System.out.print(" ");
      }
      System.out.println();
      return;
    }
    for (int i = 2; i <= sum; i++) {
      // 当前数还未放入结果集中，放入进行测试，若不行则回溯
      if(!marked[i]){
        marked[i] = true;
        result[n+1] = i;
        PrimeRing(sum, n+1);
        // 如果递归函数跳出，说明当前自然数不合理，没有存入结果集，撤销其标记
        result[n+1] = 0;
        marked[i] = false;
      }
    }
  }
  

- 图遍历

• 题目描述

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

• 问题简述：

  • m 行 n 列的二维数组，其中 * 代表空格，@代表目标点；
  • 1 <= m, n <= 100；
  • 对于图中连通的@点（其中横向、纵向、对角线相邻都视为连通），属于同一个deposit，计算整个图中deposit的个数；
  • 抽象理解，即求一个【非连通图中的连通分量个数】；
  • 这类【将相邻的点联合成一个块】的算法有一个专门的名词——Flood Fill，它常作为某些算法的预处理方式使用。

• 解题思路1（错误示例）：

  • 最开始看到此题，我想使用【暴力循环】的方法求解：

    • 设置二维标记数组、所在deposit的标记数组
    • 遍历整个图，对于图中的每个’@'节点：
      • 再次遍历整个图中，与此点连通且已经标记（已经在结果集中）的’@'点
      • 将两点标记到同一个deposit中，并将当前点标记为已访问
      • 如果找不到目标’@'点，则将当前点放到一个新的deposit中
    • 但根据下图所示的结果，发现这种算法有很大缺陷——无法提前判断一行中两个距离很远的点是否会因为后面行中的’@'而形成连通，所以本来在一个deposit中的点也会被误判。

  • 测试用例：
    

  • 对于上例，测试结果及标记数组为：
    

• 解题思路2：

  • 因此，更换解题思路，使用bfs的思想，对于图中每个未访问过的’@‘点，使用递归的方法，将与其连通的所有’@‘点都一次性标记，直到访问完全部节点，此时每个’@'点都被标记到一个deposit中。
  • 代码逻辑：
    • 设置如下所示的几个静态变量：
      • block_mark 存储每个节点所属的连通分量编号，只对’@‘节点有效，’*'节点对应-1；
      • deposit_cnt 记录当前连通分量个数；
      • graph_queue 用于bfs存储要扩展的节点坐标；
      • graph_options 用于记录bfs的 8 个扩展方向；
    • 在bfs函数中，当队列非空，分别针对 8 个方向判断是否可扩展，并刷新队列内容；
    • Main 函数中，首先初始化静态变量，然后针对图中每个【未标记的’@‘节点】进行bfs扩展，将与其连通的所有’@'节点划分到同一个连通分量中。
  • 代码：

  //要使用的静态变量
  private static int[][] block_mark;
  private static int deposit_cnt = 0;
  private static Queue<int[]> graph_queue  = new LinkedList<>();
  private static int[][] graph_options = {
    {-1, 0},{-1, 1},{0, 1},{1, 1},
    {1, 0},{1, -1},{0, -1},{-1, -1},
  };
  /**
   * 使用bfs的方法解决非连通图问题
   * @param graph 非连通图
   * @param m 图的行数
   * @param n 图的列数
   */
  private static void GraphRecursive(char[][] graph, int m, int n){
    if(graph_queue.isEmpty()) return;
    while (!graph_queue.isEmpty()){
      int[] curr = graph_queue.poll();
      int x = curr[0], y = curr[1];
      for (int[] option: graph_options) {
        int a = x+option[0], b = y+option[1];
        if(a>=m || b>=n || a<0 || b<0) continue;
        // 找到与当前点连通的未标记@点
        if(graph[a][b]=='@' && block_mark[a][b]==-1){
          block_mark[a][b] = block_mark[x][y];
          int[] item = new int[]{a, b};
          graph_queue.offer(item);
        }
      }
    }
  }
  
  public static void main(String[] args) {
    char[][] graph = new char[][]{
      {'*', '*', '*', '*', '@'},
      {'*', '@', '@', '*', '@'},
      {'*', '@', '*', '*', '@'},
      {'@', '@', '@', '*', '@'},
      {'@', '@', '*', '*', '@'},
    };
    //        char[][] graph = new char[][]{
    //                {'*', '@', '*', '@', '*'},
    //                {'*', '*', '@', '*', '*'},
    //                {'*', '@', '*', '@', '*'},
    //        };
    int m = 5, n = 5;
    block_mark = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        block_mark[i][j] = -1;
      }
    }
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if(graph[i][j]=='@'&&block_mark[i][j]==-1){
          graph_queue.clear();
          int[] item = new int[]{i, j};
          graph_queue.offer(item);
          block_mark[i][j] = deposit_cnt;
          // 调用bfs函数
          GraphRecursive(graph, m, n);
          deposit_cnt++;
        }
      }
    }
    System.out.println("Num of deposit is "+deposit_cnt);
    for (int[] i:block_mark) {
      for (int ii: i) {
        System.out.print(ii+"\t");
      }
      System.out.println();
    }
  }
  

• 解题思路3：

  • 除了使用bfs外，王道中还展示了递归（dfs）算法的实现，思路与bfs非常相似，只是在进行连通点扩展时使用递归函数而不是队列；

  • 使用递归的主要好处是，相比bfs，代码更为简洁清晰，不需要额外维护一个queue对象；

  • 当然，在使用递归时尤其需要注意递归层数，因为程序能使用的栈空间有限，因此若递归层数过深将会导致栈溢出，程序无法通过测试；

  • 代码逻辑：

    • 设置如下所示的几个静态变量：
      • graph_mark 记录每个节点是否被标记；
      • deposit_cnt 记录当前连通分量个数；
      • graph_options 用于记录 8 个扩展方向；
    • 其余逻辑与bfs类似，见如下代码；

  • 代码：

    private static boolean[][] graph_mark;
    private static int deposit_cnt = 0;
    private static int[][] graph_options = {
      {-1, 0},{-1, 1},{0, 1},{1, 1},
      {1, 0},{1, -1},{0, -1},{-1, -1},
    };
    /**
     * 使用递归（dfs）方法解决非连通图问题
     * @param graph 非连通图
     * @param m 图的行数
     * @param n 图的列数
     * @param x 当前点横坐标
     * @param y 当前点纵坐标
     */
    private static void GraphRecursive(char[][] graph, int m, int n, int x, int y){
      for (int[] option: graph_options) {
        int a = x+option[0], b = y+option[1];
        if(a>=m || b>=n || a<0 || b<0) continue;
        // 找到与当前点连通的未标记@点
        if(graph[a][b]=='@' && !graph_mark[a][b]){
          graph_mark[a][b] = true;
          GraphRecursive(graph, m, n, a, b);
        }
      }
    }
    public static void main(String[] args) {
      /** 
      变量初始化过程略
      **/
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
          if(graph[i][j]=='@'&&!graph_mark[i][j]){
            graph_mark[i][j] = true;
            // 调用递归函数
            GraphRecursive(graph, m, n, i, j);
            deposit_cnt++;
          }
        }
      }
      System.out.println("Num of deposit is "+deposit_cnt);
    }
    

4. DFS

- 算法

• 与 BFS 相对应，广搜按层次遍历所有状态，而深搜则优先遍历层次更深的状态，直到遇到一个状态结点，其不再拥有子树，则返回上一层，访问其未被访问过的子树，直至解答树中所有的状态都被遍历完毕；
• 因此，每发现一个新状态，都针对其进行更深层次的扩展，而最先遇到的状态则可能靠后进行扩展；
• 在 BFS 中，利用【队列】先进先出的特性实现层次遍历，而在 DFS 中，则通常使用【堆栈】，先进后出，实现深度搜索；
• DFS 的两种实现方式：
  • 利用堆栈，先进后出，保存和扩展搜索过程中得到的状态；
  • 使用递归实现；
• 通常使用 DFS 解决“有或没有”的问题（注意BFS是求最优解）。

- 迷宫问题II

• 题目描述：

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze. The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

• 问题简述：

  • N 行 M 列的二维迷宫，‘S’ 标记起点，‘D’ 标记终点，‘X’ 标记墙（不能通行），’.’ 标记路（可以通行）；
  • 定义每移动一步（只能上、下、左、右四个方向）耗费 1 个单位的时间；
  • 要求迷宫中每个格子只能访问一次；
  • 给定时间 T，求解能否从起点出发，刚好在时间 T 到达终点。

• 解题思路：

  • 类似 BFS，首先分析问题中的状态，即为每个可以到达的格子的位置及所用时间；
  • 对于状态扩展方式，根据题意限定，每次移动只有 4 个可行的方向，并耗费一个单位的时间；
  • 设置静态变量，存储迷宫数组、行列数、限定时间、以及 success 标记能否找到出口；
  • 在 DFS 递归函数中，扩展四个方向的移动点，判断下一位置是否到达终点：
    • 若到达，则 success 标记为 true，结束递归；
    • 若未到达，将当前位置置为 ‘X’，作为访问标记，进行当前位置的深度扩展；
    • 若扩展结束仍未找到问题解，则将当前位置恢复为 ‘.’，取消访问标记；
    • 每次递归结束都判断一次是否找到解（success是否为true），若找到解，结束递归。

• 代码：

  // DFS迷宫问题静态变量
  private static char[][] maze_graph;
  private static int N, M, T;
  private static int[][] maze_options = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  private static boolean success = false;
  
  /**
   * 通过递归实现DFS找迷宫出口
   * @param x 当前所在位置横坐标
   * @param y 纵坐标
   * @param t 到当前位置所需步数
   */
  private static void DFSMaze(int x, int y, int t){
    for (int[] option: maze_options) {
      int a = x + option[0], b = y + option[1];
      // 若下一扩展位置出界、遇到墙或遇到起点，则跳过
      if(a<0||b<0||a>=N||b>=M||maze_graph[a][b]=='X'||maze_graph[a][b]=='S') continue;
      // 规定时间到达终点
      if(maze_graph[a][b]=='D'&&t+1==T){
        success = true;
        return;
      }
      maze_graph[a][b] = 'X';
      DFSMaze(a, b, t+1);
      maze_graph[a][b] = '.';
      if (success) return;
    }
  }
  public static void main(String[] args) {
   //        maze_graph = new char[][]{
  //                {'S', '.', 'X', '.'},
  //                {'.', '.', 'X', '.'},
  //                {'.', '.', 'X', 'D'},
  //                {'.', '.', '.', '.'},
  //        };
    maze_graph = new char[][]{
      {'S', '.', 'X', '.'},
      {'.', '.', 'X', '.'},
      {'.', '.', '.', 'D'},
    };
    N = 3; M = 4; T = 5;
    DFSMaze(0, 0, 0);
    System.out.println((success?"YES":"NO"));
  }