我的递归可以吗?是否有任何破坏代码的示例?

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( 的元素到具有 target=60，但不存在从同一元素到目标=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);
}

是否有任何错误和禁忌会破坏代码？我对递归不太好。

Answer 1

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

1  1  1  1
1  0  0  1
1  0  0  0
1  1  1  2

您的代码将遵循路径 {0,0}->{0,1}->{0,2}->{0,3}->{1,3}->{2,3}，然后返回 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 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;
}