algorithm - 递归实现东北路径的麻烦

Question

我应该使用递归来输出从 A 点到 B 点的唯一东北路径 ne(x, y) 的总数，其中 B 是 A 以北的 x 行和 A 以东的 y 列。此外，我需要打印可能的唯一 NE 路径。

我知道如何使用递归来获取唯一路径的总数。但是，我坚持使用递归正确打印所有 NE 路径。

这是一些测试用例的给定输出： 输出图像

无论如何，这是我错误的递归代码的屏幕截图。请给我建议我哪里出错了。我已经为此花费了很多时间，但仍然无法找到解决方案。

Answer 1

1. 我认为您应该打印 if( rows == 0 && cols == 0 )，因为当您到达 B 点时就是这种情况。
   
2. 为什么在第一个 ne 调用中使用 path+="N" 作为回报？这会将“N”添加到原始路径，然后您将在第二次调用中获得路径+“N”+“E”。

尝试以下操作：

public static int ne( int rows, int cols, String path )
{
   if( rows == 0 && cols == 0 )
   {
      System.out.println(path);
      return 1;
   }
   int npats = 0, wpaths = 0;
   if( rows != 0 )
      npaths = ne( rows-1, cols, path+"N" );
   if( cols != 0 )
      wpaths = ne( rows, cols-1, path+"E" );
   return npaths + wpaths;
}