Force deduction solution summary 675- cutting trees for golf competition

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

You're invited to cut trees for a forest that's going to hold a golf game . The forest consists of a  m x n The matrix representation of , In this matrix ：

0 Indicates an obstacle , Can't touch
1  Represents the ground , Can walk
Than 1 Large number   Represents a cell with a tree , Can walk , The value represents the height of the tree
Each step , You can go up 、 Next 、 Left 、 Move one unit in one of the four directions to the right , If there is a tree where you stand , Then you can decide whether to cut it down .

You need to cut down all the trees from low to high according to the height of the tree , Every time I cut a tree , The value of this cell becomes 1（ It becomes the ground ）.

You will (0, 0) Start work at , Return to the minimum number of steps you need to take to cut down all trees . If you can't cut all the trees , return -1 .

What can be guaranteed is , No two trees are the same height , And you need to cut down at least one tree .

Example 1：

Input ：forest = [[1,2,3],[0,0,4],[7,6,5]]
Output ：6
explain ： Follow the path above , You can use it. 6 Step , Cut down the trees from the lowest to the highest .
Example 2：

Input ：forest = [[1,2,3],[0,0,0],[7,6,5]]
Output ：-1
explain ： Because the middle row is blocked by obstacles , Unable to access the tree in the bottom row .
Example 3：

Input ：forest = [[2,3,4],[0,0,5],[8,7,6]]
Output ：6
explain ： You can follow the example 1 The same path to cut down all the trees .
(0,0) The trees of the location , You can cut it directly , Don't count the steps .
 

Tips ：

m == forest.length
n == forest[i].length
1 <= m, n <= 50
0 <= forest[i][j] <= 109

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/cut-off-trees-for-golf-event
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

Refer to the official explanation .

Because it needs to be cut according to the height , So it is actually to find the shortest distance between two adjacent heights .

The shortest distance between the two , We just use DP To solve the problem .

Code ：

 int[][] dirs = {
   {-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int cutOffTree(List<List<Integer>> forest) {
        List<int[]> trees = new ArrayList<int[]>();
        int row = forest.size();
        int col = forest.get(0).size();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (forest.get(i).get(j) > 1) {
                    trees.add(new int[]{i, j});
                }
            }
        }
        Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));

        int cx = 0;
        int cy = 0;
        int ans = 0;
        for (int i = 0; i < trees.size(); ++i) {
            int steps = bfs(forest, cx, cy, trees.get(i)[0], trees.get(i)[1]);
            if (steps == -1) {
                return -1;
            }
            ans += steps;
            cx = trees.get(i)[0];
            cy = trees.get(i)[1];
        }
        return ans;
    }

    public int bfs(List<List<Integer>> forest, int sx, int sy, int tx, int ty) {
        if (sx == tx && sy == ty) {
            return 0;
        }
        int row = forest.size();
        int col = forest.get(0).size();
        int step = 0;
        Queue<int[]> queue = new ArrayDeque<int[]>();
        boolean[][] visited = new boolean[row][col];
        queue.offer(new int[]{sx, sy});
        visited[sx][sy] = true;
        while (!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            for (int i = 0; i < sz; ++i) {
                int[] cell = queue.poll();
                int cx = cell[0], cy = cell[1];
                for (int j = 0; j < 4; ++j) {
                    int nx = cx + dirs[j][0];
                    int ny = cy + dirs[j][1];
                    if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
                        if (!visited[nx][ny] && forest.get(nx).get(ny) > 0) {
                            if (nx == tx && ny == ty) {
                                return step;
                            }
                            queue.offer(new int[]{nx, ny});
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }