Нахождение минимального расстояния от начальной позиции до конечной позиции - PullRequest
Новая
       4

Нахождение минимального расстояния от начальной позиции до конечной позиции

0 голосов
/ 07 ноября 2019

Как я понимаю, Breadth-First-Search может использоваться для определения минимального расстояния между начальной и конечной позициями, но по какой-то причине я не получаю кратчайшее расстояние в моей реализации. Вот источник вопроса .

Вот моя реализация: 

class Solution 
{
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) 
    {
        if(maze.empty())
            return 0;

        int steps = 0;
        int m = maze.size(), n = maze[0].size();
        std::vector<std::vector<bool>> v(m, std::vector<bool>(n, false));
        std::vector<std::vector<int>> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        std::queue<std::vector<int>> q;
        q.push(start);
        v[start[0]][start[1]] = true;

        while(!q.empty())
        {
            auto p = q.front();
            q.pop();

            if(p[0] == destination[0] && p[0] == destination[1])
                return steps;

            for(auto dir : dirs)
            {
                int x = p[0];
                int y = p[1];

                if(isValid(maze, x + dir[0], y + dir[1]))
                {
                    x += dir[0];
                    y += dir[1];
                }

                if(!v[x][y])
                {
                    v[x][y] = true;
                    q.push({x, y});
                }
            }
            steps++;
        }
        return steps;
    }

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

Теперь я знаю, что мне придется иметь дело со случаем, когда это невозможноидти от начала до конца. Но для этого теста: 

[[0,0,0,0,1,0,0],[0,0,1,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1],[0,1,0,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,1,0,0,0,1],[0,0,0,0,1,0,0]]
[0,0]
[8,6]

Я получаю 55, и ответ должен быть 26. Я не уверен, что я делаю здесь неправильно.

...