What's wrong with my standard bfs code?


  • 0
    C

    I used standard BFS. Mark every position we reach 2 to avoid repeated search. The code fails at test case 70, which is a huge one. Could anyone see mistakes in my code?

    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            int N=maze.size(), M = maze[0].size();
            int minlen=INT_MAX;
            int dx[4] ={ 1, 0,-1, 0};
            int dy[4] ={ 0, 1, 0,-1}; 
            queue<vector<int>> Q;
            Q.push({start[0],start[1],-1,0});
            maze[start[0]][start[1]] = 2;
            while( !Q.empty() ){
                vector<int> F = Q.front();
                Q.pop();
                for(int i=0;i<4;i++){
                    int x=F[0],y=F[1],last=F[2],dist=F[3];
                    if( (last==1 || last==3) && (i==1 || i==3) ) continue;
                    if( (last==0 || last==2) && (i==0 || i==2) ) continue;
                    int d=0;
                    while( x+dx[i]>=0 && x+dx[i]<N && y+dy[i]>=0 && y+dy[i]<M && maze[x+dx[i]][y+dy[i]]!=1 ){
                        x += dx[i]; y += dy[i]; d++;
                    }
                    if( x==destination[0] && y==destination[1] && dist+d<minlen) minlen=dist+d;
                    if( maze[x][y]==2 ) continue;
                    maze[x][y] = 2;
                    Q.push({x,y,i,dist+d});
                }
            }
            return minlen==INT_MAX?-1:minlen;
        }
    };
    

  • 0
    X

    you might need to re process the position again if a smaller distance is found.


  • 0
    C

    I see. Searching from a searched position might yield shorter distance.


Log in to reply
 

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