Summary of Maze I, II, III


  • 0
    D

    The Maze I, II and III problems are similar to other 2D matrix problems. The major difference is they can move more than one steps each time. The solutions are pretty similar.

    Maze I

    class Solution {
    public:
        bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            if (destination == start) return true;
            int m = maze.size(), n = (m == 0) ? 0 : maze[0].size();
            int dirs[5] = {0, 1, 0, -1, 0};
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            queue<vector<int>> q;
            q.push(start);
            while(!q.empty())
            {
                vector<int> ij = q.front(); q.pop();
                int i = ij[0], j = ij[1];
                if (i == destination[0] && j == destination[1]) return true;
                visited[i][j] = true;
                for (int d = 0; d < 4; d++)
                {
                    int x = i, y = j;
                    while(x+dirs[d] >= 0 && x+dirs[d] < m && y+dirs[d+1] >= 0 && y+dirs[d+1] < n && maze[x+dirs[d]][y+dirs[d+1]] == 0)
                    {
                        x += dirs[d], y += dirs[d+1];
                    }
                    if (!visited[x][y]) q.push(vector<int>{x, y});
                }
            }
            return false;
        }
    };
    

    Maze II

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            if (destination == start) return true;
            int m = maze.size(), n = (m == 0) ? 0 : maze[0].size();
            int dirs[5] = {0, 1, 0, -1, 0};
            vector<vector<int>> dist(m, vector<int>(n, -1));
            dist[start[0]][start[1]] = 0;
            queue<vector<int>> q;
            q.push(start);
            while(!q.empty())
            {
                vector<int> ij = q.front(); q.pop();
                int i = ij[0], j = ij[1];
                int distance = dist[i][j];
                for (int d = 0; d < 4; d++)
                {
                    int step = 0;
                    int x = i, y = j;
                    while(x+dirs[d] >= 0 && x+dirs[d] < m && y+dirs[d+1] >= 0 && y+dirs[d+1] < n && maze[x+dirs[d]][y+dirs[d+1]] == 0)
                    {
                        step++;
                        x += dirs[d], y += dirs[d+1];
                    }
                    if (dist[x][y] == -1 || dist[x][y] > distance + step) {
                        dist[x][y] = distance + step;
                        q.push(vector<int>{x, y});
                    }
                }
            }
            return dist[destination[0]][destination[1]];        
        }
    };
    

    Maze III

    class Solution {
    public:
        string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
            int m = maze.size(), n = (m == 0) ? 0 : maze[0].size();
            int dirs[5] = {0, 1, 0, -1, 0};
            char sd[4] = {'r', 'd', 'l', 'u'};
            vector<vector<pair<int, string>>> dist(m, vector<pair<int, string>>(n, {-1, ""}));
            dist[ball[0]][ball[1]].first = 0;
            queue<vector<int>> q;
            q.push(ball);
            while(!q.empty())
            {
                vector<int> ij = q.front(); q.pop();
                int i = ij[0], j = ij[1];
                int distance = dist[i][j].first;
                string s = dist[i][j].second;
                for (int d = 0; d < 4; d++)
                {
                    int step = 0;
                    int x = i, y = j;
                    string t = s + sd[d];
                    while(x+dirs[d] >= 0 && x+dirs[d] < m && y+dirs[d+1] >= 0 && y+dirs[d+1] < n && maze[x+dirs[d]][y+dirs[d+1]] == 0)
                    {
                        step++;
                        x += dirs[d], y += dirs[d+1];
                        if (x == hole[0] && y == hole[1]) break;
                    }
                    if (dist[x][y].first == -1 || 
                        dist[x][y].first > distance + step ||
                        dist[x][y].first == distance + step && dist[x][y].second > t) 
                    {
                        dist[x][y].first = distance + step;
                        dist[x][y].second = t;
                        q.push(vector<int>{x, y});
                    }
                }
            }
            return dist[hole[0]][hole[1]].second == "" ? "impossible" : dist[hole[0]][hole[1]].second;             
        }
    };
    

Log in to reply
 

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