Simple C++ BFS solution


  • 1
    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            if (maze.empty()) return false;
            int m = maze.size(), n = maze[0].size();
            vector<vector<int>> dist(m, vector<int>(n, INT_MAX)); // dist[i][j] maintain the shortest distance from start to (i,j)
            queue<pair<int,int>> q; // {i*n+j, dist}
            int go[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
            
            q.push({start[0]*n + start[1], 0});
            dist[start[0]][start[1]] = 0;
            while (!q.empty()) {
                int i = q.front().first/n, j = q.front().first%n;
                int t = q.front().second;
                q.pop();
                for (int d = 0; d < 4; ++d) {
                    int ni = i, nj = j;
                    int s = 0;
                    while (ni >= 0 && ni < m && nj >= 0 && nj < n && maze[ni][nj] == 0) {
                        ni += go[d][0]; nj += go[d][1]; ++s;
                    }
                    ni -= go[d][0]; nj -= go[d][1]; --s;
                    if (t+s >= dist[ni][nj]) continue; // if this is a longer path, no need to move on
                    else {
                        dist[ni][nj] = t+s;
                        if (ni != destination[0] || nj != destination[1]) q.push({ni*n + nj, t+s});
                    }
                }
            }
            return dist[destination[0]][destination[1]] == INT_MAX ? -1 : dist[destination[0]][destination[1]];
        }
    };
    

Log in to reply
 

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