LeetCode 675 - Cut Off Trees for Golf Event

https://www.cnblogs.com/grandyang/p/8379506.html

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:

1. 0 represents the obstacle can't be reached.
2. 1 represents the ground can be walked through.
3. 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.

https://leetcode.com/problems/cut-off-trees-for-golf-event/discuss/107404/Java-solution-PriorityQueue-%2B-BFS

1. Since we have to cut trees in order of their height, we first put trees (int[] {row, col, height}) into a priority queue and sort by height.
2. Poll each tree from the queue and use BFS to find out steps needed.

The worst case time complexity could be O(m^2 * n^2) (m = number of rows, n = number of columns) since there are m * n trees and for each BFS worst case time complexity is O(m * n) too.

class Solution {
    static int[][] dir = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};

    public int cutOffTree(List<List<Integer>> forest) {
        if (forest == null || forest.size() == 0) return 0;
        int m = forest.size(), n = forest.get(0).size();

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest.get(i).get(j) > 1) {
                    pq.add(new int[] {i, j, forest.get(i).get(j)});
                }
            }
        }

        int[] start = new int[2];
        int sum = 0;
        while (!pq.isEmpty()) {
            int[] tree = pq.poll();
            int step = minStep(forest, start, tree, m, n);

            if (step < 0) return -1;
            sum += step;

            start[0] = tree[0];
            start[1] = tree[1];
        }

        return sum;
    }

    private int minStep(List<List<Integer>> forest, int[] start, int[] tree, int m, int n) {
        int step = 0;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                if (curr[0] == tree[0] && curr[1] == tree[1]) return step;

                for (int[] d : dir) {
                    int nr = curr[0] + d[0];
                    int nc = curr[1] + d[1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n 
                        || forest.get(nr).get(nc) == 0 || visited[nr][nc]) continue;
                    queue.add(new int[] {nr, nc});
                    visited[nr][nc] = true;
                }
            }
            step++;
        }

        return -1;
    }

http://www.programmersought.com/article/222929242/

Give an int two-dimensional array representing the height of the tree at position i j , 0 is unreachable, 1 is flat. Cut the trees in order from short to high. Ask to take at least a few steps to finish.

Using a priority queue to find which tree we would cut. Using BFS to find the shortest steps. Using int[] store the postion and height of a tree. Add all of them into pq with ascending sorting.

Then preform BFS to find the steps needed to get the next position.

这道题让我们砍掉所有高度大于1的树，而且要求是按顺序从低到高来砍，那么本质实际上还是要求任意两点之间的最短距离啊。对于这种类似迷宫遍历求最短路径的题，BFS是不二之选啊。那么这道题就对高度相邻的两棵树之间调用一个BFS，所以我们可以把BFS的内容放倒子函数helper中来使用。那么我们首先就要将所有的树从低到高进行排序，我们遍历原二位矩阵，将每棵树的高度及其横纵坐标取出来，组成一个三元组，然后放到vector中，之后用sort对数组进行排序，因为sort默认是以第一个数字排序，这也是为啥我们要把高度放在第一个位置。然后我们就遍历我们的trees数组，我们的起始位置是（0，0），终点位置是从trees数组中取出的树的位置，然后调用BFS的helper函数，这个BFS的子函数就是很基本的写法，没啥过多需要讲解的地方，会返回最短路径的值，如果无法到达目标点，就返回-1。所以我们先检查，如果helper函数返回-1了，那么我们就直接返回-1，否则就将cnt加到结果res中。然后更新我们的起始点为当前树的位置，然后循环取下一棵树即可

https://www.acwing.com/solution/LeetCode/content/534/

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个非负的二维数组表示，在这个数组中：

• 0 表示 障碍，无法触碰到。
• 1 表示可以行走的 地面。
• 比 1 大的数 表示一颗允许走过的 树 的，这个整数表示数的高度。

你被要求按照树的高度从低向高砍掉所有的树，每砍过一颗树，树的高度变为 1。

你将从（0，0）点开始工作，你应该返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵 树 的高度是相同的，并且至少有一颗树需要被砍。

1. 首先将所有的树和坐标放到一个数组中，并且按照高度从小到大排序。
2. 接着遍历每一棵树，并通过BFS计算出从上一棵树走到这一棵树需要的最少步数；若无法达到，则答案就是 -1。

https://leetcode.com/articles/cutoff-trees-for-golf-event/
http://reeestart.me/2018/04/22/LeetCode-675-Cut-Off-Trees-for-Golf-Event/

X, Videos
花花酱 LeetCode 675. Cut Off Trees for Golf Event - 刷题找工作 EP55

LeetCode 773 - Sliding Puzzle

https://www.cnblogs.com/grandyang/p/8955735.html

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.

Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.

Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]

Input: board = [[3,2,4],[1,5,0]]
Output: 14

Note:

• board will be a 2 x 3 array as described above.
• board[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].

https://leetcode.com/problems/sliding-puzzle/discuss/146652/Java-8ms-BFS-with-algorithm-explained

Consider each state in the board as a graph node, we just need to find out the min distance between start node and final target node "123450". Since it's a single point to single point questions, Dijkstra is not needed here. We can simply use BFS, and also count the level we passed. Every time we swap 0 position in the String to find the next state. Use a hashTable to store the visited states.

public int slidingPuzzle(int[][] board) {
        String target = "123450";
        String start = "";
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                start += board[i][j];
            }
        }
        HashSet<String> visited = new HashSet<>();
        // all the positions 0 can be swapped to
        int[][] dirs = new int[][] { { 1, 3 }, { 0, 2, 4 },
                { 1, 5 }, { 0, 4 }, { 1, 3, 5 }, { 2, 4 } };
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);
        int res = 0;
        while (!queue.isEmpty()) {
            // level count, has to use size control here, otherwise not needed
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)) {
                    return res;
                }
                int zero = cur.indexOf('0');
                // swap if possible
                for (int dir : dirs[zero]) {
                    String next = swap(cur, zero, dir);
                    if (visited.contains(next)) {
                        continue;
                    }
                    visited.add(next);
                    queue.offer(next);

                }
            }
            res++;
        }
        return -1;
    }

    private String swap(String str, int i, int j) {
        StringBuilder sb = new StringBuilder(str);
        sb.setCharAt(i, str.charAt(j));
        sb.setCharAt(j, str.charAt(i));
        return sb.toString();
    }

https://leetcode.com/problems/sliding-puzzle/discuss/113620/Java-19ms-26-clean-lines-BFS-w-comment-Time-and-space%3A-O(4320).

Convert array to string, e.g., [[1,2,3],[4,0,5]] -> "123405", hence the corresponding potential swap displacements are: -1, 1, -3, 3. Also note, charAt(2) and charAt(3) are not adjacent in original 2 dimensional int array and therefore are not valid swaps.

    private static final int[] d = { 1, -1, 3, -3 }; // potential swap displacements.
    public int slidingPuzzle(int[][] board) {
        // convert board to string - initial state.
        String s = Arrays.deepToString(board).replaceAll("\\[|\\]|,|\\s", "");
        Queue<String> q = new LinkedList<>(Arrays.asList(s)); // add initial state to queue.
        Set<String> seen = new HashSet<>(q); // used to avoid duplicates
        int ans = 0; // record the # of rounds of Breadth Search
        while (!q.isEmpty()) { // Not traverse all states yet?
            // loop used to control search breadth.
            for (int sz = q.size(); sz > 0; --sz) { 
                String str = q.poll();
                if (str.equals("123450")) { return ans; } // found target.
                int i = str.indexOf('0'); // locate '0'
                for (int k = 0; k < 4; ++k) { // traverse all options.
                    int j = i + d[k]; // potential swap index.
                    // conditional used to avoid invalid swaps.
                    if (j < 0 || j > 5 || i == 2 && j == 3 || i == 3 && j == 2) { continue; } 
                    char[] ch = str.toCharArray();
                    // swap ch[i] and ch[j]:  ch[i] = ch[j], ch[j] = '0'. Updated per @caowang888's suggestion. 
                    ch[i] = ch[j];
                    ch[j] = '0';
                    s = String.valueOf(ch); // a new candidate state.
                    if (seen.add(s)) { q.offer(s); } //Avoid duplicate.
                }
            }
            ++ans; // finished a round of Breadth Search, plus 1.
        }
        return -1;
    }

Analysis:
There are at most 6! permutation of the 6 numbers: 0~5. For each permustion, cost spaceO(6); String.indexOf() and String.equals() cost time O(6). Therefore, space and time both cost 6 * 6! = 4320.

Time & space: O(4320).

Feel free to let me know if you can find a tighter bound.

Update:
2
Question: Can you explain how did u determine the potential swap distance?

Answer:

When you map a 2 dimensional ( row * column ) matrix to 1 dimensional array, the swap to left and right are still -1 and 1 respectively in terms of index change in 1-D array. In contrast, the swap to up and down are -column and column as of index change.

That is, for any given index (i, j) in the matrix, it will be mapped to (i * column + j) in the array. Since in the matrix (i, j) could swap with (i, j - 1), (i, j + 1), (i - 1, j), and (i + 1, j), in the array (i * column + j) would swap with (i * column + j - 1), (i * column + j + 1), ((i - 1) * column + j) and ((i + 1) * column + j) accordingly.

We can easily conclude the swap displacement are -1, 1, -column, and column correspondingly.

e.g.: Let's consider (1, 2) in the following 3 * 5 matrix

column # -->               0     1     2     3     4
                      0  (0,0) (0,1) (0,2) (0,3) (0,4)
                      1  (1,0) (1,1) (1,2) (1,3) (1,4)
                      2  (2,0) (2,1) (2,2) (2,3) (2,4)

we can swap (1, 2) with (1, 1), (1, 3), (0, 2), and (2, 2)

When mapped to 1 dimensional array, it can be obtained that (1 * 5 + 2) swap with (1 * 5 + 2 - 1), (1 * 5 + 2 + 1), ((1 - 1) * 5 + 2) and ((1 + 1) * 5 + 2):

  0    1    2    3    4    5    6    7    8    9   10   11   12   13   
(0,0)(0,1)(0,2)(0,3)(0,4)(1,0)(1,1)(1,2)(1,3)(1,4)(2,0)(2,1)(2,2)(2,3)

 14
(2,4)

Obviously, we can swap 7 with, 6 (= 7 - 1), 8 (= 7 + 1), 2 (= 7 - 5), 12 (= 7 + 5), where 5 is matrix column (width).

The displacements in the above case are -1, 1, -5, and 5.

http://www.noteanddata.com/leetcode-773-Sliding-Puzzle-java-solution-note.html

public int slidingPuzzle(int[][] board) {
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < board.length; ++i) {
        for(int j = 0; j < board[i].length; ++j) {
            sb.append(board[i][j]);
        }
    }

    String init = sb.toString();
    Queue<String> queue = new LinkedList<>();
    queue.add(init);
    Set<String> visited = new HashSet<>();
    visited.add(init);
    /*
    index map
    [0,1,2],
    [3,4,5]
    */
    int[][] dirs = {
        {1,3},  // 0 can to 1 and 3
        {0,2,4},
        {1,5},
        {0,4},
        {1,3,5},
        {2,4}
    };

    int steps = 0;
    while(!queue.isEmpty()) {
        Queue<String> nextQueue = new LinkedList<>();
        while(!queue.isEmpty()) {
            String cur = queue.poll();
            if("123450".equals(cur)) {
                return steps;
            }
            int zeroIndex = cur.indexOf('0');
            for(int nextIndex: dirs[zeroIndex]) {
                char[] arr = cur.toCharArray();
                arr[zeroIndex] = arr[nextIndex];
                arr[nextIndex] = '0';
                String next = new String(arr);
                if(!visited.contains(next)) {
                    nextQueue.add(next);
                    visited.add(next);
                }
            }
        }
        queue = nextQueue;
        steps++;
    }
    return -1;
}

这个就是大家都玩过的滑块游戏，有个0表示空格，每次可以把这个空格和其他的一个相邻的位置进行交换。问最后能不能出现第一排第二排依次是"123450"的结局。如果不能，则返回-1；如果可以，需要返回所需要的最少步数。

Hard题目真的是一个比一个看起来难，但是只要有充足的经验，能看出这个是考BFS的题目，那么剩下的时间就是套用模板了吧。。

每次移动都相当于得到了一个新的状态，同时记录得到这个状态需要的步数，并把这个状态保存到已经出现过的set里。所以，本题的难点在于使用如果把二维数组和字符串进行转化的问题，代码写的很清楚了，就不详细说了。

需要注意的是，通过二维坐标得到字符串索引的方式是x * cols + y，我觉得应该是常识，可是我第一次没想出来。

Ps，吐槽一句，python的字符画不支持直接指定某个位置的字符，因此这个题里面迫不得已用了几次string和list互转的过程。。

最坏情况下的时间复杂度是O((MN)!)，空间复杂度是O(MN)。M,N代表行列数，这个题分别为2，3.

看到这道题不禁让博主想起了文曲星上的游戏-华容道，好吧，又暴露年龄了|||-.-，貌似文曲星这种电子辞典神马的已经是很古老的东西了，但是上面的一些经典游戏，什么英雄坛说啊，华容道啊，虽然像素分辨率低的可怜，画面效果连小霸王学习机其乐无穷都比不上，更不要说跟现在的什么撸啊撸，吃鸡之类的画面相比了，但是却给初高中时代的博主学习之余带来了无限的乐趣。不过这题跟华容道还是有些不同的，因为那个游戏各块的大小不同，而这道题的拼图大小都是一样的。那么像这种类似迷宫遍历的问题，又要求最小值的问题，要有强烈的BFS的感觉，没错，这道题正是用BFS来解的。这道题好就好在限定了棋盘的大小，是2x3的，这就让题目简单了许多，由于0的位置只有6个，我们可以列举出所有其下一步可能移动到的位置。为了知道每次移动后拼图是否已经恢复了正确的位置，我们肯定需要用个常量表示出正确位置以作为比较，那么对于这个正确的位置，我们还用二维数组表示吗？也不是不行，但我们可以更加简洁一些，就用一个字符串 "123450"来表示就行了，注意这里我们是把第二行直接拼接到第一行后面的，数字3和4起始并不是相连的。好，下面来看0在不同位置上能去的地方，字符串长度为6，则其坐标为 012345，转回二维数组为：

0  1  2
3  4  5

那么当0在位置0时，其可以移动到右边和下边，即{1, 3}位置；在位置1时，其可以移动到左边，右边和下边，即{0, 2, 4}位置；在位置2时，其可以移动到左边和下边，即{1, 5}位置；在位置3时，其可以移动到上边和右边，即{0, 4}位置；在位置4时，其可以移动到左边，右边和上边，即{1, 3, 5}位置；在位置5时，其可以移动到上边和左边，即{2, 4}位置。

然后就是标准的BFS的流程了，使用一个HashSet来记录访问过的状态，将初始状态start放入，使用一个queue开始遍历，将初始状态start放入。然后就是按层遍历，取出队首状态，先和target比较，相同就直接返回步数，否则就找出当前状态中0的位置，到dirs中去找下一个能去的位置，赋值一个临时变量cand，去交换0和其下一个位置，生成一个新的状态，如果这个状态不在visited中，则加入visited，并且压入队列queue，步数自增1。如果while循环退出后都没有回到正确状态，则返回-1，参见代码如下：

int slidingPuzzle(vector<vector<int>>& board) {
    int res = 0, m = board.size(), n = board[0].size();
    string target = "123450", start = "";
    vector<vector<int>> dirs{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            start += to_string(board[i][j]);
        }
    }
    unordered_set<string> visited{start};
    queue<string> q{{start}};
    while (!q.empty()) {
        for (int i = q.size() - 1; i >= 0; --i) {
            string cur = q.front(); q.pop();
            if (cur == target) return res;
            int zero_idx = cur.find("0");
            for (int dir : dirs[zero_idx]) {
                string cand = cur;
                swap(cand[dir], cand[zero_idx]);
                if (visited.count(cand)) continue;
                visited.insert(cand);
                q.push(cand);
            }
        }
        ++res;
    }
    return -1;
}

上面的解法虽然很炫，但是有局限性，比如若棋盘很大的话，难道我们还手动列出所有0能去的位置么？其实我们可以使用最普通的BFS遍历方式，就检查上下左右四个方向，那么这样我们就不能压缩二维数组成一个字符串了，我们visited数组中只能放二维数组了，同样的，queue 中也只能放二维数组，由于二维数组要找0的位置的话，还需要遍历，为了节省遍历时间，我们将0的位置也放入queue中，那么queue中的放的就是一个pair对儿，保存当前状态，已经0的位置，初始时将棋盘以及0的位置排入queue中。之后的操作就跟之前的解法没啥区别了，只不过这里我们的心位置就是上下左右，如果未越界的话，那么和0交换位置，看新状态是否已经出现过，如果这个状态不在visited中，则加入visited，并且压入队列queue，步数自增1。如果while循环退出后都没有回到正确状态，则返回-1，参见代码如下：

int slidingPuzzle(vector<vector<int>>& board) {
    int res = 0;
    set<vector<vector<int>>> visited;
    queue<pair<vector<vector<int>>, vector<int>>> q;
    vector<vector<int>> correct{{1, 2, 3}, {4, 5, 0}};
    vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[i][j] == 0) q.push({board, {i, j}});
        }
    }
    while (!q.empty()) {
        for (int i = q.size() - 1; i >= 0; --i) {
            auto t = q.front().first;
            auto zero = q.front().second; q.pop();
            if (t == correct) return res;
            visited.insert(t);
            for (auto dir : dirs) {
                int x = zero[0] + dir[0], y = zero[1] + dir[1];
                if (x < 0 || x >= 2 || y < 0 || y >= 3) continue;
                vector<vector<int>> cand = t;
                swap(cand[zero[0]][zero[1]], cand[x][y]);
                if (visited.count(cand)) continue;
                q.push({cand, {x, y}});
            }
        }
        ++res;
    }
    return -1;
}

X. Videos
花花酱 LeetCode 773. Sliding Puzzle - 刷题找工作 EP167