C++ Simple Solution, Concise Code


  • 0

    bfs

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            int m = maze.size(), n = m ? maze[0].size() : 0;
            pair<int, int> end = {destination[0], destination[1]};
            vector<vector<int>> dis(m, vector<int>(n , -1));
            vector<pair<int, int>> neis = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            queue<pair<int, int>> qu;
            qu.push({start[0], start[1]});
            dis[start[0]][start[1]] = 0;
            
            while (qu.size()) {
                int r = qu.front().first, c = qu.front().second;
                qu.pop();
                
                for (auto nei : neis) {
                    int row = r, col = c, move = 0;
                    while (row + nei.first >= 0 && row + nei.first < m 
                            && col + nei.second >= 0 && col + nei.second < n && maze[row + nei.first][col + nei.second] != 1) {
                        row += nei.first;
                        col += nei.second;
                        move++;
                    }
                    if (dis[row][col] == -1 || dis[row][col] > move + dis[r][c]) {
                        qu.push({row, col});
                        dis[row][col] = move + dis[r][c];
                    }
                }
            }
            return dis[destination[0]][destination[1]];
        }
    };
    

    bfs by steps

    class Solution {
        bool isWall(vector<vector<int>>& maze, int r, int c) {
            int m = maze.size(), n = maze[0].size();
            if (r < 0 || r >= m || c < 0 || c >= n || maze[r][c] == 1)
                return true;
            return false;
        }
        
        int intValueOfDirection(pair<int, int> direction) {
            if (direction.first == 0) {
                if (direction.second == 1) {
                    return 0;
                } else {
                    return 1;
                }
            } else {
                if (direction.second == 1) {
                    return 2;
                } else {
                    return 3;
                }
            }
            return -1;
        }
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            
            queue<pair<int, int>> st_point;
            queue<pair<int, int>> st_direction;
            queue<int> st_dis;
            unordered_map<int, unordered_map<int, unordered_map<int, int>>> mp;
            
            vector<pair<int, int>> neis = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            pair<int, int> end = {destination[0], destination[1]};
            
            for (auto nei : neis) {
                st_point.push({start[0], start[1]});
                st_direction.push(nei);
                st_dis.push(0);
            }
            
            while (st_dis.size()) {
                pair<int, int> point = st_point.front(), direction = st_direction.front();
                int dis = st_dis.front();
                st_point.pop();
                st_direction.pop();
                st_dis.pop();
                
                if (isWall(maze, point.first, point.second) || (mp[point.first][point.second].find(intValueOfDirection(direction)) != mp[point.first][point.second].end() && mp[point.first][point.second][intValueOfDirection(direction)] < dis))
                    continue;
                mp[point.first][point.second][intValueOfDirection(direction)] = dis;
                if (isWall(maze, point.first + direction.first, point.second + direction.second)) {
                    //
                    if (point == end)
                        return dis;
                    for (auto nei : neis) {
                        st_point.push({point.first + nei.first, point.second + nei.second});
                        st_direction.push(nei);
                        st_dis.push(dis + 1);
                    }
                } else {
                    st_point.push({point.first + direction.first, point.second + direction.second});
                    st_direction.push(direction);
                    st_dis.push(dis + 1);
                }
                
            }
            
            return -1;
        }
    };
    

    dfs

    class Solution {
        void dfs(vector<vector<int>>& maze, vector<vector<int>>& dis, int row, int col) {
            int m = maze.size(), n = m ? maze[0].size() : 0;
            vector<pair<int, int>> neis = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (auto nei : neis) {
                int r = row, c = col, move = 0;
                while (r + nei.first >= 0 && r + nei.first < m && c + nei.second >= 0 && c + nei.second < n && maze[r + nei.first][c + nei.second] != 1) {
                    r += nei.first;
                    c += nei.second;
                    move++;
                }
                if (dis[r][c] == -1 || dis[r][c] > dis[row][col] + move) {
                    dis[r][c] = dis[row][col] + move;
                    dfs(maze, dis, r, c);
                }
            }
        }
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            int m = maze.size(), n = m ? maze[0].size() : 0;
            vector<vector<int>> dis(m, vector<int>(n, -1));
            dis[start[0]][start[1]] = 0;
            
            dfs(maze, dis, start[0], start[1]);
            
            return dis[destination[0]][destination[1]];
        }
    };
    

Log in to reply
 

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