2
\$\begingroup\$

I solved this LeetCode Challenge:

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

0 represents the obstacle can't be reached. 1 represents the ground can be walked through. The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree's height. You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:
Input: 
[
 [1,2,3],
 [0,0,4],
 [7,6,5]
]
Output: 6
Example 2:
Input: 
[
 [1,2,3],
 [0,0,0],
 [7,6,5]
]
Output: -1
Example 3:
Input: 
[
 [2,3,4],
 [0,0,5],
 [8,7,6]
]
Output: 6
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.

Hint: size of the given matrix will not exceed 50x50.

My solution is very intuitive in that it scans the entire tree to create the order of trees to be cut initially.

The I run a bfs between the current position and the next tree that needs to be cut.

Is it possible to optimize the solution like a better search strategy or use any alternative algorithm to pre-compute the distance between two trees?

class Solution {
public:

    int cutOffTree(vector<vector<int>>& forest) {
        auto order = TreeOrder(forest);
        int answer = 0;
        auto front = order.begin();
        if(front->second.first != 0 || front->second.second != 0)
        {
            int dist = bfs(forest, make_pair(0, 0), front->second);
            if(dist == -1) return dist;
            answer += dist;
        }
        int count = order.size();
        int current = 0;
        while(current < count - 1)
        {
            auto from = order.begin()->second;
            order.erase(order.begin());
            auto to = order.begin()->second;
            int dist = bfs(forest, from, to);
            if(dist == -1) return dist;
            answer += dist;
            ++current;
        }
        return answer;
    }
    set<pair<int,pair< int, int> > > TreeOrder(vector<vector<int>>& forest)
    {
        set<pair < int, pair< int, int>>> order;
        for(int i=0; i< forest.size(); ++i)
        {
            for(int j=0; j< forest[0].size(); ++j)
            {
                if(forest[i][j] > 1)
                {
                    order.insert(make_pair(forest[i][j], make_pair(i,j)));    
                }
            }
        }

        return order;
    }
    int bfs(vector<vector<int>>& forest, pair<int, int> start, pair<int, int> end)
    {
        int max_row = forest.size(), max_col = forest[0].size();
        vector<vector<bool>> visited(forest.size(), vector<bool>(forest[0].size(), false));
        queue<pair<int,pair<int, int>>> active;
        active.push(make_pair(0, start));
        while(!active.empty())
        {
            auto front = active.front();
            active.pop();
            int row = front.second.first, col = front.second.second;
            if(row == end.first && col == end.second)
            {
                return front.first;
            }
            //Right 
            if(col + 1 < max_col && !visited[row][col + 1] && forest[row][col + 1])
            {
                visited[row][col + 1] = true;
                active.push(make_pair(front.first + 1, make_pair(row, col + 1)));
            }
            //Left
            if(col - 1 >= 0  && !visited[row][col - 1] && forest[row][col - 1])
            {
                visited[row][col + 1] = true;
                active.push(make_pair(front.first + 1, make_pair(row, col - 1)));
            }
            //Top
            if(row - 1 >= 0  && !visited[row - 1][col] && forest[row -1][col])
            {
                visited[row - 1][col] = true;
                active.push(make_pair(front.first + 1, make_pair(row -1, col)));
            }
            //Bottom
            if(row + 1 < max_row  && !visited[row + 1][col] && forest[row +1][col])
            {
                visited[row + 1][col] = true;
                active.push(make_pair(front.first + 1, make_pair(row + 1, col)));
            }
        }
        return -1;
    }    


};
\$\endgroup\$
-2
\$\begingroup\$

basically first store in increasing order of tree heights as map key with a dfs and values as index of that tree.

Start from current location and find shortest route to next big tree with a djikstra like approach.

http://writeulearn.com/leetcode-add-search-word-data-structure-design-cpp/#Cut_Off_Trees_for_Golf_Event

\$\endgroup\$
  • 1
    \$\begingroup\$ Link-only answers are discouraged in part because links can become stale or broken, and also because it doesn't really provide a review of the code in question. See How do I write a good answer? for reference. \$\endgroup\$ – dfhwze Jun 26 at 19:12
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Jun 27 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.