c - 矩阵中N步的最长路径

Question

给定一个起始单元格，我试图在 RxC 矩阵中找到一条长度为 N 的简单路径。路径应遵循由布尔函数给出的限制。目标是稍后使用它来找到矩阵中的最长路径。

我设置了一个解决方案，但是我不知道如何修改它以知道解决方案何时不存在。

我的解决方案包括使用回溯的 DFS 方法。当有一个时，解决方案是正确的，但程序返回找到的最长路径，而不是说这样的路径不存在。

我知道可用的解决方案存在类似的问题，但我想了解我的逻辑在哪里失败。

这是代码（我们可以从一个单元格中向所有 8 个方向移动）：

Bool DFS(Map *map,Point* srcPt,short steps,Bool (*restrictionCompare)(Point *p1, Point *p2))
{
    Point *target;
    short row = getPointRow(srcPt);
    short col = getPointCol(srcPt);

    // Found N-steps path!
    if (steps == 0)
    {
        puts("Path found!\n");
        return 1;
    }


    //Mark the M[row][col] as visited
    markAsVisited(map,row,col);


    // Iterate over all 8 directions of a cell
    for (short i = 0; i < DIRECTIONS; ++i)
    {
        short coords[2];
        // Get a valid adjacent cell
        if (getNeighbour(map,srcPt,i,coords,restrictionCompare) == FALSE) continue;

        target = getMapPoint(map,coords[0],coords[1]); // This is the valid neighbour


        //if cell wasn't visited before...
        if (isVisited(target) == FALSE)
        {

            // ..recursively call DFS from cell
            if(DFS(map,target,--steps,restrictionCompare) == TRUE)
            {

                // Show point
                showPoint(target);

                return TRUE;
            }                     
        }

    }

    // Backtrack
    markAsUnvisited(map,row,col);
    return FALSE;
}

程序找到的长度路径示例：

也欢迎任何有关如何提高代码效率的建议。

标签： calgorithmdepth-first-searchbacktracking