C++, BFS, 6 ms concise solution


  • 1
    Z

    I have tried BFS, DFS, and Dijkstra with priority_queue. And it came out BFS is fastest, at least in C++. Possible reason is that BFS is better than DFS for shortest path problem, and DFS results in many useless travel through the graph. And it seems that the priority_queue grows quickly for Dijkstra algorithm, because the same point with different distance was all put in the queue.

    Similar to other two Maze problems, I use 1 matrix to save minimum distance from starting points (initially INT_MAX), and 1 matrix to save the path to current point. I use a queue to perform BFS. A new point will be added into the queue, if the new distance is less than saved or the distance is the same but the new path is lexicographically smaller. When the hole is encountered, update the distance and path of the hole, and go to next iteration.

    The time complexity is hard to analyze. The worst case could be O(mn*mn), m and n is the size of maze.

    class Solution {
    public:
        string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
            int m = maze.size(), n = maze[0].size();
            vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
            vector<vector<string>> path(m, vector<string>(n));
            // distance of starting point is 0
            dis[ball[0]][ball[1]] = 0;
            queue<vector<int>> myq;
            myq.push(ball);
           // the order of ball move direction is lexicographically smallest, i.e. dlru
            vector<int> d1({1, 0, 0, -1}), d2({0, -1, 1, 0});
            string dirs = "dlru";
            while (!myq.empty()) {
                int row = myq.front()[0], col = myq.front()[1];
                myq.pop();
                for (int i = 0; i < 4; ++i) {
                    int r = row+d1[i], c = col+d2[i], len = 0;
                    while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
                        r += d1[i];
                        c += d2[i];
                        len++;
                    }
                    r -= d1[i];
                    c -= d2[i];
                    // if the current move goes across the hole
                    if ((hole[0]-row)*(hole[0]-r) <= 0 && (hole[1]-col)*(hole[1]-c) <= 0) {
                        int k = abs(hole[0]-row)+abs(hole[1]-col);
                        if (dis[hole[0]][hole[1]] > dis[row][col]+k || (dis[hole[0]][hole[1]] == dis[row][col]+k && path[hole[0]][hole[1]] > path[row][col]+dirs[i])) {
                            dis[hole[0]][hole[1]] = dis[row][col]+k;
                            path[hole[0]][hole[1]] = path[row][col]+dirs[i];
                        }
                        continue;
                    }
                    // check whether the end point should be a new starting point
                    if (dis[r][c] > dis[row][col]+len || (dis[r][c] == dis[row][col]+len && path[r][c] > path[row][col]+dirs[i])) {
                        dis[r][c] = dis[row][col]+len;
                        path[r][c] = path[row][col]+dirs[i];
                        myq.push({r, c});
                    }
                }
            }
            return path[hole[0]][hole[1]] == ""? "impossible":path[hole[0]][hole[1]];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.