C++ BFS with optimization, 86ms beats 100%
If you are going from (x1,y1) to (x2,y2), instead of doing 4-direction (up,down,left,right) BFS, we can first do 2-direction BFS to see if there exists a shorte
If you are going from (x1,y1) to (x2,y2), instead of doing 4-direction (up,down,left,right) BFS, we can first do 2-direction BFS to see if there exists a shortest path from source to destination.\n\ne.g. going from S(x1,y1) to T(x2,y2) we know we have to take lower-right direction, that is, either go right or down. ```'X'``` is obstacle, ```'*'``` is current layer, shortest length = 5, going step by step as follow:\n```\n[S, , , ]     [ ,*, , ]    [ , ,*, ]    [ , , ,*]    [ , , , ]    [ , , , ]\n[ , ,X, ] ->  [*, ,X, ] -> [ ,*,X, ] -> [ , ,X, ] -> [ , ,X,*] -> [ , ,X, ]\n[X, , ,T]     [X, , ,T]    [X, , , ]    [X,*, , ]    [X, ,*, ]    [X, , ,*]     \n```\nIf there is no shortest path available and have to make a detour, then we have to do conventional BFS.\ne.g.\n```\n[ ,X, , , ]\n[ ,S, ,X, ]\n[ , , ,X, ] \n[ , ,X, ,T]     \n[X, , , , ] \n```\nThis is very efficient if obstacle is sparse in the forest.\n```\nclass Solution {\npublic:\n    int cutOffTree(vector<vector<int>>& forest) {\n        vector<vector<int>> trees; //vector<[height,i,j]>\n        for(int i=0; i<forest.size(); ++i)\n            for(int j=0; j<forest[0].size(); ++j)\n                if(forest[i][j]>1)\n                    trees.push_back(vector<int>({forest[i][j],i,j}));\n        sort(trees.begin(),trees.end(),[](vector<int>& a, vector<int>& b){\n            return a[0]<b[0]; //sort by tree's height\n        });\n        \n        //doing DFS to see if every tree is available from (0,0)\n        int tree_available = 0;\n        vector<vector<bool>> visited(forest.size(),vector<bool>(forest[0].size(),false));\n        DFS(0,0,visited,forest,tree_available);\n        if(tree_available != trees.size())   return -1; //some trees are not available from (0,0)\n        \n        int step = 0;\n        int si=0, sj=0;\n        for(int i=0; i<trees.size(); ++i){\n            // optimization here, if there are no obstacles blocking the shortest path, return the shortest length \n            // no need to do the 4-direction BFS\n            if(ShortestPathAvailable(si,sj,trees[i][1],trees[i][2],forest))\n                step += abs(si-trees[i][1])+abs(sj-trees[i][2]);\n            else\n                step += BFS(si,sj,trees[i][1],trees[i][2],forest);\n            si = trees[i][1];\n            sj = trees[i][2];\n        }\n        \n        return step;\n    }\n    \n    void DFS(int i, int j, vector<vector<bool>>& visited, const vector<vector<int>>& forest, int& count){\n        if(i<0 || i>=forest.size() || j<0 || j>=forest[0].size() || visited[i][j] || forest[i][j]==0)  return;\n        visited[i][j] = true;\n        if(forest[i][j]>1)  count++;\n        DFS(i+1,j,visited,forest,count);\n        DFS(i-1,j,visited,forest,count);\n        DFS(i,j+1,visited,forest,count);\n        DFS(i,j-1,visited,forest,count);\n    }\n    \n    //return the minimum step from (si,sj) to (ti,tj)\n    int BFS(int si, int sj, int ti, int tj, const vector<vector<int>>& forest){\n        vector<vector<bool>> visited(forest.size(),vector<bool>(forest[0].size(),false));\n        visited[si][sj] = true;\n        queue<pair<int,int>> q({make_pair(si,sj)});\n        int len = 0;\n        int di[4] = {1,0,-1,0};\n        int dj[4] = {0,1,0,-1};\n        while(true){\n            int qsize = q.size();\n            while(qsize--){\n                if(q.front().first==ti && q.front().second==tj) //the function stops here\n                    return len; \n                for(int k=0; k<4; ++k){\n                    int i=q.front().first+di[k];\n                    int j=q.front().second+dj[k];\n                    if(i>=0 && i<forest.size() && j>=0 && j<forest[0].size() && !visited[i][j] && forest[i][j]>0){\n                        visited[i][j] = true;\n                        q.push(make_pair(i,j));\n                    }\n                }\n                q.pop();\n            }\n            ++len;\n        }\n        return -999999; //redundancy, never goes this line\n    }\n    \n    // check if there exists a shortest path avail from (x1,y1) to (x2,y2) going one out of 4 directions :\n    // upper-left , upper-right , lower-left , lower-right\n    /*  e.g. going from S(x1,y1) to T(x2,y2), 'X' is obstacle, '*' is current layer\n        lower-right direction, minumum step = 5, going step by step as follow\n        [S, , , ]     [ ,*, , ]    [ , ,*, ]    [ , , ,*]    [ , , , ]    [ , , , ]\n        [ , ,X, ] ->  [*, ,X, ] -> [ ,*,X, ] -> [ , ,X, ] -> [ , ,X,*] -> [ , ,X, ]\n        [X, , ,T]     [X, , , ]    [X, , , ]    [X,*, , ]    [X, ,*, ]    [X, , ,*]     \n                        step 1       step 2       step 3       step 4       step 5\n    */\n    bool ShortestPathAvailable(int x1, int y1, int x2, int y2, const vector<vector<int>>& forest){\n        int dx = (x2>x1)? 1 : -1;\n        int dy = (y2>y1)? 1 : -1;\n        int minstep = abs(x1-x2)+abs(y1-y2);\n        queue<pair<int,int>> q({make_pair(x1,y1)});\n        while(minstep--){\n            int qsize = q.size();\n            if(qsize==0) \n                return false; //haven't gone minstep yet, but no path available\n            while(qsize--){\n                int x = q.front().first;\n                int y = q.front().second;\n                q.pop();\n                if(x!=x2 && forest[x+dx][y]>0 && ((x+dx)!=q.back().first || y!=q.back().second))\n                    q.push(make_pair(x+dx,y));\n                if(y!=y2 && forest[x][y+dy]>0 && (x!=q.back().first || (y+dy)!=q.back().second))\n                    q.push(make_pair(x,y+dy));\n            }\n        }\n        return q.size()==1; //if true return, only destination [x2,y2] is in the queue\n    }\n};\n```
[]