1

有人可以帮助解决以下面试问题：

设为a矩阵MxN。使用以下原型编写一个函数：

void PrintAllPaths(int** a, int M, int N, int x, int y) {};

打印矩阵中从左下角(0,0)到右下角的所有路径，这些路径沿途(M-1,N-1)通过点(x,y)。在路径的每一步，一个人只能向右或向下走。样本：

PrintAllPaths (a, 3, 3, 1, 2);

应该打印：

(0,0)(0,1)(0,2)(1,2)(2,2)
(0,0)(0,1)(1,1)(1,2)(2,2)
(0,0)(1,0)(1,1)(1,2)(2,2)

我有几个想法：

  1. 查找从 to 的所有路径和从(0,0)to 的所有(x,y)路径。以某种方式从这两个路径中制作笛卡尔积。(x,y)(M-1,N-1)

  2. 使用矩阵a进行回溯。我想它可以使用，因为该函数的打印输出不依赖于 a 中的数据。(a,M,N,x,y)通过向右递归求解和(a,M,N-1,x,y-1)向下递归求解来求解(a,M-1,N,x-1,y)。

但是，我在实现这一点时遇到了问题。我无法正确跟踪路径。有人可以帮助编写代码（或更好的想法）吗？

4

1 回答 1

0

同时，我终于设法将想法 2 转换为工作代码。我没有使用矩阵a进行路径回溯，因为它不是必需的。它仍然相当复杂，所以如果有人有更优雅的解决方案，请发布！

#include <stdio.h>
#include <string.h>

void PrintAllPaths(int **a, int M, int N, int x, int y) {
    static char Path[500]="(0,0)"; //keeps path for currently processed recursion
    static int m=M, n=N; //keep initial values of M and N
    static bool passedXY=false; //have we passed (x,y) along current path?

    if ((x<0 || y<0) && (passedXY==false)) { return;} //missed (X,Y), so skip
    if (x==0 && y==0) passedXY=true;

    if ((M==1 && N==1)) {puts(Path); return;};  //we have made N-1 steps down and M-1 steps right, so we reached (M-1,N-1) and we print path

    //try to go right   
    if (N>1) {
        char temp[10];
        sprintf(temp,"(%d,%d)",m-M,n-N+1); //add point to the right to the path
        strcat(Path,temp);
        PrintAllPaths(a, M, N-1, x, y-1);  //go right
        Path[strlen(Path)-5]='\0';  //remove last point from the path, since it is processed
        if ((x>0 && y>=0)||(x>=0 && y>0)) passedXY=false; //reset passedXY value if needed
    };

    //try to go down
    if (M>1) {
        char temp[10];
        sprintf(temp,"(%d,%d)",m-M+1,n-N);
        strcat(Path,temp);
        PrintAllPaths(a, M-1, N, x-1, y); 
        Path[strlen(Path)-5]='\0';
        if ((x>0 && y>=0)||(x>=0 && y>0)) passedXY=false;
    }

};


int main() {
int **a=0;
PrintAllPaths(a, 3, 3, 1, 2);
char ch='a'; scanf("%c",ch);
}
于 2013-11-05T01:18:50.227 回答