时间戳

首页 > 解决方案 > 我的递归好吗？有没有破坏代码的例子？

c++ - 我的递归好吗？有没有破坏代码的例子？

问题描述

给定一个整数方阵 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) 的元素到目标 = 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);
}

是否存在破坏代码的错误和反例？我不太擅长递归。

标签： c++matrixpathmaze

解决方案

考虑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;
}

推荐阅读