PINEAL.ME   Archives  About

Shortest Path

Maze I

bool hasPath(vector<vector<int>> & maze, vector<int> & start, vector<int> & dest) {
    const vector<int> dx = {0, -1, 1, 0};
    const vector<int> dy = {1, 0, 0, -1};
    queue<pair<int, int>> q;
    q.emplace(start[0], start[1]);
    maze[start[0]][start[1]] = 2;
    int m = maze.size();
    int n = maze.front().size();
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = cur.first;
        int y = cur.second;
        if (x == dest[0] && y == dest[1]) {
            return true;
        }

        for (int i = 0; i < 4; i++) {
            int xx = x;
            int yy = y;
            while (xx >= 0 && xx < m && yy >= 0 && yy < n && maze[xx][yy] != 1) {
                xx += dx[i];
                yy += dy[i];
            }
            xx -= dx[i];
            yy -= dy[i];
            if (maze[xx][yy] == 0) {
                maze[xx][yy] = 2;
                q.emplace(xx, yy);
            }
        }
    }
    return false;
}

Maze II

struct Position {
    int x, y, d;
    Position(int x, int y, int d): x(x), y(y), d(d) {}
};

class Solution {
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& dest) {
        if (maze.empty()) {
            return -1;
        }
        auto cmp = [](Position & p1, Position & p2) {return p1.d > p2.d;};
        priority_queue<Position, vector<Position>, decltype(cmp)> pq(cmp);
        pq.emplace(Position(start[0], start[1], 0));
        
        int m = maze.size();
        int n = maze.front().size();
        
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        const vector<int> dx = {0, 1, -1, 0};
        const vector<int> dy = {1, 0, 0, -1};
        while (!pq.empty()) {
            auto p = pq.top();
            pq.pop();
            int x = p.x;
            int y = p.y;
            int d = p.d;
            if (x == dest[0] && y == dest[1]) {
                return d;
            }
            dis[x][y] = d;
            for (int i = 0; i < 4; i++) {
                int nx = x;
                int ny = y;
                int nd = d;
                while (nx + dx[i] < m && nx + dx[i] >= 0 && ny + dy[i] < n && ny + dy[i] >= 0 
                       && maze[nx + dx[i]][ny + dy[i]] == 0) {
                    nx += dx[i];
                    ny += dy[i];
                    nd++;
                }
                if (dis[nx][ny] > nd) {
                        dis[nx][ny] = nd;
                        pq.emplace(Position(nx, ny, nd));
                }
            }
        }
        return -1;   
    }
};

Maze III

struct State
{
    int x;
    int y;
    int d;
    State (int x, int y, int d) : x(x), y(y), d(d) {}
};

const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, -1, 1};
const string dirs = "dulr";
    
class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        auto cmp = [](State & s1, State & s2) {
            return s1.d > s2.d;  
        };
        priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);
        pq.emplace(ball[0], ball[1], 0);
        int m = maze.size();
        int n = maze.front().size();
        //dis[x][y]=>maintain the shortest distance to the source so far
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        //dir[x][y]=>maintain the lexicographically smallest way from the source so far
        vector<vector<string>> way(m, vector<string>(n));
        while(!pq.empty()) {
            auto state = pq.top();
            pq.pop();
            int x = state.x;
            int y = state.y;
            int d = state.d;
            if (d > dis[x][y]) {
                continue;
            }
            string path = way[x][y];
            dis[x][y] = d;
            if (x == hole[0] && y == hole[1]) {
                return way[x][y];
            }
            for (int i = 0; i < 4; i++) {
                int nx = x;
                int ny = y;
                int nd = d;
                string path = way[x][y] + dirs[i]; 
                while (nx + dx[i] < m && nx + dx[i] >= 0 && ny + dy[i] < n && ny + dy[i] >= 0 
                       && maze[nx + dx[i]][ny + dy[i]] == 0) {
                    nx += dx[i];
                    ny += dy[i];
                    nd++;
                    if (nx == hole[0] && ny == hole[1]) {
                        break;
                    }
                }
                if (nd < dis[nx][ny]) {
                    dis[nx][ny] = nd;
                    way[nx][ny] = path;
                    pq.emplace(nx, ny, nd);
                }
                if (nd == dis[nx][ny]) {
                    if (path < way[nx][ny]) {
                        way[nx][ny] = path;
                    }
                }
            }
        }
        return "impossible";
    }
};

Leetcode 317: Shortest Distance from All Buildings

找到一个点,从他开始到所有的buildings的距离最短的和,中间有障碍物。对每个点做BFS,然后加起来求一个最小值。这样的时间复杂度是 $O(m*n)[BFS] * O(m*n)[matrix] = O(m^2*n^2)$。优化:从building开始搜。那么时间复杂度为$O(k*m*n)$。 $k$ 是 building 的个数。

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int res = INT_MAX;
        
        vector<vector<pair<int, int>>> dis(grid.size(), vector<pair<int, int>>(grid[0].size()));    
        //dis[i][j].first => total distance from k buildings to grid[i][j]
        //dis[i][j].second => num of times search from k buildings and visited to grid[i][j] successfully (avoid dead end)
        int m = grid.size();
        int n = grid[0].size();
        int num_buildings = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    bfs(grid, dis, i, j);
                    num_buildings++;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dis[i][j].second == num_buildings) {
                    res = min(res, dis[i][j].first);
                }
            }
        }
        return res == INT_MAX? -1 : res;
    }
    
    
    void bfs(const vector<vector<int>> & grid, vector<vector<pair<int, int>>> & dis, int i, int j) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int m = grid.size();
        int n = grid[0].size();
        deque<deque<bool>> visited(m, deque<bool>(n, false));
        
        vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        
        int level = 0;      //distance to building in grid[i][j]
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                if (level != 0) {
                    dis[x][y].first += level;
                    dis[x][y].second++;
                }
                for (const auto & dir : dirs) {
                    int x_prime = x + dir.first;
                    int y_prime = y + dir.second;
                    if (x_prime < m && x_prime >= 0 && y_prime < n && y_prime >= 0 && 
                        grid[x_prime][y_prime] == 0 &&
                        visited[x_prime][y_prime] == false) {
                        q.emplace(x_prime, y_prime);
                        visited[x_prime][y_prime] = true;
                    }
                }    
            }            
            level++;
        }
        
    }
};

Best Meeting Point

和上题一样的做法,只是可以在人所在的位置。做BFS标记visited的时候要注意。

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        int res = INT_MAX;        
        vector<vector<int>> dis(grid.size(), vector<int>(grid[0].size()));    
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    bfs(grid, dis, i, j);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                    res = min(res, dis[i][j]);
            }
        }
        return res == INT_MAX? -1 : res;        
    }
    void bfs(const vector<vector<int>> & grid, vector<vector<int>> & dis, int i, int j) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int m = grid.size();
        int n = grid[0].size();
        deque<deque<bool>> visited(m, deque<bool>(n, false));
        visited[i][j] = true;
        vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        
        int level = 0;      //distance to grid[i][j]
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                if (level != 0) {
                    dis[x][y] += level;
                }
                for (const auto & dir : dirs) {
                    int x_prime = x + dir.first;
                    int y_prime = y + dir.second;
                    if (x_prime < m && x_prime >= 0 && y_prime < n && y_prime >= 0 && 
                        visited[x_prime][y_prime] == false) {
                        q.emplace(x_prime, y_prime);
                        visited[x_prime][y_prime] = true;
                    }
                }    
            }            
            level++;
        }
    }    
};

但超时啦。 答案里给的方法是算出median。并不适用有obstacle的情况(是嘛?)。

// Time:  O(mn)
// Space: O(m+n)
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> x, y;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j]) {
                    x.emplace_back(i);
                    y.emplace_back(j);
                }
            }
        }
        nth_element(x.begin(), x.begin() + x.size() / 2, x.end());
        nth_element(y.begin(), y.begin() + y.size() / 2, y.end());
        const int mid_x = x[x.size() / 2];
        const int mid_y = y[y.size() / 2];
        int sum = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j]) {
                    sum += abs(mid_x - i) + abs(mid_y - j);
                }
            }
        }
        return sum;
    }
};

数学证明参考链接

Dijkstra

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/

https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

https://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/

A star

https://github.com/pineal/-O_O-/blob/master/A_Star_Search/A_Star_Search.cpp

BFS