Самый длинный путь с N ступенями в матрице - PullRequest
Новая
       38

Самый длинный путь с N ступенями в матрице

0 голосов
/ 18 мая 2019

Я пытаюсь найти простой путь длины N в матрице RxC, учитывая начальную ячейку. Путь должен следовать ограничению, заданному логической функцией. Цель состоит в том, чтобы позже использовать это, чтобы найти самый длинный путь в матрице.

Я установил решение, но я не знаю, как его изменить, чтобы узнать, когда решения не существует.

Мое решение состоит из подхода 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;
}

Пример пути длины, найденного программой:

path

Любые предложения о том, как повысить эффективность кода, также приветствуются.

...