Алгоритм поиска кратчайшего пути в сетке - PullRequest
Новая
       69

Алгоритм поиска кратчайшего пути в сетке

0 голосов
/ 25 января 2020

Фон:

Проблема от leetcode :

В квадратной сетке N на N каждая ячейка либо пустой (0) или заблокированный (1).

A очистить путь от левого верхнего до нижнего правого имеет длину k тогда и только тогда, когда он состоит из ячеек C_1, C_2, ..., C_k так что:

  • Смежные ячейки C_i и C_{i+1} соединены в 8 направлениях (ie., они разные и имеют общий край или угол)
  • C_1 находится в местоположении (0, 0) (ie. имеет значение grid[0][0])
  • C_k находится в местоположении (N-1, N-1) (ie. имеет значение grid[N-1][N-1])
  • Если C_i находится в (r, c), то grid[r][c] пусто (ie. grid[r][c] == 0).

Возвращает длину кратчайшего такого чистого пути сверху слева до внизу справа. Если такой путь не существует, верните -1. ​​

Вопрос:

Я был совершенно уверен, что мой алгоритм был верным, но для этого теста: 

[[0,1,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,1,1,1,0],[0,1,0,0,0]]

Я получаю 9, и правильный ответ - 7. Есть ли что-то, что я делаю неправильно в приведенном ниже коде?

Код: 

class Solution {
public:
    std::vector<std::vector<int>> dirs = {{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid.empty())
            return 0;

        if(grid[0][0] == 1 || grid[grid.size()-1][grid.size()-1] == 1) 
            return -1;


        int m = grid.size(), n = grid[0].size();
        std::pair<int, int> start = {0,0};
        std::pair<int, int> end = {m-1, n-1};
        std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
        std::priority_queue<std::pair<int,int>> q;
        q.push(start);
        visited[start.first][start.second] = true;
        int count = 1;

        while(!q.empty())
        {
            auto cur = q.top();
            q.pop();

            if(cur.first == end.first && cur.second == end.second)
                return count;

            for(auto dir : dirs)
            {
                int x = cur.first, y = cur.second;

                if(isValid(grid, x + dir[0], y + dir[1]))
                    x += dir[0], y += dir[1];

                if(!visited[x][y])
                {
                    visited[x][y] = true;
                    q.push({x,y});
                }
            }
            count++;
        }
        return -1;
    }

    bool isValid(std::vector<std::vector<int>>& grid, int i, int j)
    {
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size() || grid[i][j] != 0)
            return false;
        return true;
    }
};

1 Ответ

2 голосов
/ 25 января 2020

Это не проблема, для которой вы бы использовали алгоритм Дейкстры. Этот алгоритм предназначен для взвешенных графиков, в то время как проблема, с которой вы сталкиваетесь, это невзвешенные . Более того, то, как вы используете приоритетную очередь, неверно. Очередь приоритетов C ++ по умолчанию извлекает элемент, который large , но, поскольку вы предоставляете его координаты, это означает, что он вытолкнет элемент с наибольшими координатами. Это явно не то, что вам нужно. На самом деле, у вас нет ничего, чтобы упорядочить узлы, поскольку эта проблема касается невзвешенного графика.

Во-вторых, count подсчитывает общее количество посещаемых вами узлов. Это не может быть правдой, поскольку вы наверняка также посещаете узлы, которые не находятся на кратчайшем пути, который вы в конечном итоге найдете.

Эта проблема решается с помощью стандартного поиска в глубину. Вы можете сделать это с двумя векторами (нет необходимости в стеке, очереди или деке, ...): второй вектор заполняется невидимыми соседями всех узлов первого. После завершения этого цикла вы заменяете первый вектор вторым, создаете новый второй вектор и повторяете ..., пока не найдете целевой узел. Количество повторений этого (внешнего) повторения соответствует длине пути.

Вот ваша shortestPathBinaryMatrix функция с необходимыми адаптациями для ее работы: 

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if(grid.empty())
        return 0;

    if(grid[0][0] == 1 || grid[grid.size()-1][grid.size()-1] == 1) 
        return -1;

    int m = grid.size(), n = grid[0].size();
    pair<int, int> start = {0,0};
    pair<int, int> end = {m-1, n-1};
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    // no priority queue needed: the graph is not weighted
    vector<std::pair<int,int>> q;
    q.push_back(start);
    visited[start.first][start.second] = true;
    int count = 1;

    while(!q.empty())
    {
        // just iterate the vector and populate a new one
        vector<std::pair<int,int>> q2;
        for(auto const& cur: q) {
            if(cur.first == end.first && cur.second == end.second)
                return count;
            for(auto dir : dirs)
            {
                int x = cur.first, y = cur.second;

                if(isValid(grid, x + dir[0], y + dir[1]))
                    x += dir[0], y += dir[1];

                if(!visited[x][y])
                {
                    visited[x][y] = true;
                    q2.push_back({x,y});
                }
            }
        }
        count++;
        q = q2; // prepare for next iteration
    }
    return -1;
}
...