C++ DFS solution


  • 2
    Z

    The idea is that each time hit a wall, turn to only two directions not the whole four directions. For example if the current move is up, then next move cannot be up or down, because it will move back.

    class Solution {
    public:
        string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
            maze[hole[0]][hole[1]] = 2; // tag the hole as 2
    
            // walk through all the maze needs this much distance
            int minDis = maze.size() * maze[0].size(); 
            string res;
            vector<char> movements;
            for (char dir : "dlru") {
                helper(ball, maze, dir, movements, 0, minDis, res);
            }
    
            if (res.empty())
                return "impossible";
            return res;
        }
    
        struct MoveStatus {
            int dis;
            bool reachHole;
        };
    
        void helper(vector<int> ball, vector<vector<int>> &maze, char dir, vector<char> &movements, int preDis, int &minDis, string &res) {
            // since move() changes ball position, need save the original position
            // not tag the ball position as visited because this move can be invalid
            int oriX = ball[0], oriY = ball[1];
    
            MoveStatus ms = move(ball, maze, dir);
            if (ms.dis == 0) // invalid move
                return;
    
            int distance = ms.dis + preDis;
            if (distance > minDis)
                return;
    
            movements.push_back(dir);
            if (ms.reachHole) {
                if (distance < minDis) {
                    minDis = distance;
                    res = string(movements.begin(), movements.end());
                }
                movements.pop_back();
                return;
            }
    
            // now tag the start point of the ball as visited
            maze[oriX][oriY] = -1;
            for (char newDir : getDir(dir)) {
                helper(ball, maze, newDir, movements, distance, minDis, res);
            }
            movements.pop_back();
            maze[oriX][oriY] = 0;
        }
    
        MoveStatus move(vector<int> &ball, vector<vector<int>> &maze, char dir) {
            int xInc = 0, yInc = 0;
            if (dir == 'u') {
                xInc = -1;
            } else if (dir == 'd') {
                xInc = 1;
            } else if (dir == 'l') {
                yInc = -1;
            } else {
                yInc = 1;
            }
    
            int &x = ball[0], &y = ball[1];
            int dis = 0;
            while (x >= 0 && x < (int)maze.size() && y >= 0 && y < (int)maze[0].size() && maze[x][y] == 0) {
                ++dis;
                x += xInc;
                y += yInc;
            }
    
            if (x >= 0 && x < (int)maze.size() && y >= 0 && y < (int)maze[0].size()) {
                if (maze[x][y] == -1)
                    return {0, false}; // cycle detected
                if (maze[x][y] == 2)
                    return {dis, true}; // reach hole
            }
    
            // touch board or wall, need go back a cell
            --dis;
            x -= xInc;
            y -= yInc;
            return {dis, false};
        }
    
        string getDir(char dir) {
            if (dir == 'u' || dir == 'd')
                return "lr";
            return "du";
        }
    };
    

Log in to reply
 

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