我的递归可以吗？有没有破解代码的例子？

Question

给定一个正方形整数矩阵A NxN，2<=N<=100 表示一个迷宫。矩阵中值大于0的元素是可以通过的，其他元素是不可以通过的。递减路径是由可通过元素形成的迷宫中的每条路径，其中每个下一个元素都在前一个元素的右侧或下方。

写一个函数bool reachable(int A[][100], unsigned N, int sx, int sy, int target)，检查是否存在从坐标为(sx,sy)的元素到值为"target"的元素的递减路径，其中路径的元素形成非递减序列。

例如：

 1  0  1  0

10 15  1  1

50 20 50 50

40  0 40 60

存在从坐标为 (0,0) 的元素到坐标为 (0,0) 的元素的路径 target=60，但不存在从同一元素到 target=40 的元素的路径。

所以这是我的尝试：

#define N 4
#include <iostream>
bool reachable(int A[N][N], int n, int x, int y, int target)
{
    if (x < 0 || y < 0 || x >= n || y >= n) return false;  
    if (A[x][y] == target) return true;

    if (A[x][y] <= A[x][y + 1])
    {
        if (reachable(A, n, x, y + 1, target)) return true;
        else return false;
    }
    if (A[x][y] <= A[x + 1][y])
    {
        if (reachable(A, n, x + 1, y, target)) return true;
        else return false;     
    }
    return true;
}
int main()
{
    int A[N][N] = { { 1, 0, 2, 0},
                    {10,15, 2, 2},
                    {50,20,50,50},
                    {40, 0,40,60} };
    std::cout << reachable(A, N, 0, 0, 60);
}

有没有破解代码的bug和反例？我不太擅长递归。

Answer 1

考虑对该矩阵的调用 reachable(A, N, 0, 0, 2)：

您的代码将遵循路径 {0,0}->{0,1}->{0,2}->{0,3}->{1,3}->{2,3 } 和 return false 之后。出现这个问题是因为这条语句：

if (A[x][y] <= A[x][y + 1])
{
  if (reachable(A, n, x, y + 1, target)) return true;
  else return false;
}

如果输入此 if-else 语句，代码将忽略下一个，它会检查其他可能的路径。所以在我的例子中，第二条路径被完全忽略了。

这是固定的变体：

添加检查如果 y==n-1 则不能右转，如果 x==n-1 则不能下转；
在递归调用后删除了错误的 return 语句；
为案例添加了最后一个 return 语句 return false，当不存在从当前点出发的路径时

bool reachable(int A[N][N], int n, int x, int y, int target)
{
  if (x < 0 || y < 0 || x >= n || y >= n)
    return false;

  if (A[x][y] == target)
    return true;

  // if possible to turn right, check this path
  if (y + 1 < n && A[x][y] <= A[x][y + 1])
  {
    if (reachable(A, n, x, y + 1, target))
      return true;
  }

  // if possible to turn down, check this path
  if (x + 1 < n && A[x][y] <= A[x + 1][y])
  {
    if (reachable(A, n, x + 1, y, target))
      return true;
  }

  // no path exists
  return false;
}

我的递归可以吗？有没有破解代码的例子？

Is my recursion ok? Are there any examples that break the code?

c++

maze

path

matrix