AM 789. The Maze III

需要多一个状态矩阵表示 方向

Code(Language:C++) (Judger:cloudjudge-cluster-9)

class Solution {
public:
    /**
     * @param maze: the maze
     * @param ball: the ball position
     * @param hole: the hole position
     * @return: the lexicographically smallest way
     */
    struct node{
        int x, y; 
        node(int x, int y){
            this->x = x; 
            this->y = y; 
        }
    }; 
    
    const vector<int> dx = {-1, 1, 0, 0};
    const vector<int> dy = {0, 0, -1, 1};
    const string movs = "udlr"; //错误 把这里写错了，debug了半小时，简直不能忍！！！！
    const int dir = 4;
    
    bool canStop(int x, int y, vector<vector<int>> &maze){
        if(x < 0 || y < 0 || x >= maze.size() || y >= maze[0].size() || maze[x][y] == 1){
            return true; 
        } 
        return false; 
    }
    
    string findShortestWay(vector<vector<int>> &maze, vector<int> &ball, vector<int> &hole) {
        // write your code here
         // write your code here
        const int m = maze.size();
        const int n = maze[0].size(); 
        std::queue<node> q; //放入queue的都是可以stop的地方
        q.push(node(ball[0], ball[1])); 
        
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX)); // status matrix to save distance along the path 
        vector<vector<string>> movDir(m, vector<string>(n, "")); // moving directions 
        
        dis[ball[0]][ball[1]] = 0; 
        maze[ball[0]][ball[1]] = 2; 
        
    
        string res = ""; 
        int resDis = INT_MAX; 
        while(!q.empty()){
            node tmp = q.front();
            q.pop();
            //if(tmp.x == destination[0] && tmp.y == destination[1]){
            //    res = min(res, dis[tmp.x][tmp.y]); 
            //}
            for(int i = 0; i < dir; i++){
                int newX = tmp.x; 
                int newY = tmp.y; 
                
                int pathLen = 0; 
                while(!canStop(newX + dx[i], newY + dy[i], maze)){
                    newX += dx[i];
                    newY += dy[i];
                    pathLen++; 
                    if(newX == hole[0] && newY == hole[1]){//arrive at hole 
                        
                        if(resDis > dis[tmp.x][tmp.y] + pathLen){
                            resDis = dis[tmp.x][tmp.y] + pathLen;
                            res = movDir[tmp.x][tmp.y] + movs[i];
                        }
                        else if(resDis == dis[tmp.x][tmp.y] + pathLen){
                            res = min(res, movDir[tmp.x][tmp.y] + movs[i]);
                        }

                    }
                }
                //错误：这里不能放在
                //if(maze[newX][newY] == 2){
                //    continue; 
                //} 后面啊
                
                if(dis[newX][newY] > dis[tmp.x][tmp.y] + pathLen){
                    dis[newX][newY] = dis[tmp.x][tmp.y] + pathLen; // update when sh orter distance available
                    movDir[newX][newY] = movDir[tmp.x][tmp.y] + movs[i]; 
                }
                else if(dis[newX][newY] == dis[tmp.x][tmp.y] + pathLen){
                    movDir[newX][newY] = min(movDir[newX][newY], movDir[tmp.x][tmp.y] + movs[i]); // update the moving directions 
                }
                
                if(maze[newX][newY] == 2){
                    continue; 
                }
                maze[newX][newY] = 2; 
                q.push(node(newX, newY)); 
                
                
                
            }
        }
        //return res == INT_MAX ? -1 : res; 
        return res == "" ? "impossible" : res; 
    }
};