OA原题描述参考：

注意：具体抽到的题目可能会有细微变化。

让小明帮公司球场修场地，给一个二维的链表fields，场地里有坑，不能走。 场地里有树要砍掉。最后目的返回是修好一层的场地的最小步数。

public int flatFields (int numRows, int numColumns, List<List<Integer>> fields) {}. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

Ex1:

[1, 3, 0, 2].

[1, 1, 3, 1]

上图中的1代表平地，可以走。 0代表坑，不能走。 大于1的数字代表树木，需要砍掉。规则是从上下左右四个角开始任选一个开始走，先砍数字小的树木。 比如2 < 3，那么就得先走2。

上图如果从右下角开始走依次经过的坐标是： （1， 3） -> (0, 3) -> (1, 3) -> (1, 2) -> (1, 1) -> (1, 0) 所以返回的最小步数是5， 因为通过这个路径可以修平第二层的球场[1, 1, 3, 1]， 并且走到左下角终点。

Ex2:

[1, 0]

[3, 2]

上图中的最小步数返回-1因为，没有办法修好一层， 因为从左上角1开始走，不能走到0， 也不能走3， 因为在全局中3比2大，必须先走2。所以就没法走了。

解题思路参考：

BFS来按照砍树顺序寻找最优路径。坑：先要找到所有树（>1的点），然后按照顺序做BFS。可以把树放到TreeMap里面（排序的HashMap）。抽到的题目可能起始点是0.0也可能是四个角，没关系把起始点都放入queue中去做BFS即可。再有注意终点可能会是最后一棵树，也可能是最优路径走出来（从最后一棵数到任意四个点的最短路径）。参考答案是从四个点开始走最后走出来的解法。

参考答案：

package com.amazon;

import java.util.*;

/**
 * Created by Tian on 2017/8/6.
 */
class Point {
    int x;
    int y;
    int val;
    Point(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

public class GolfEventMaze {
    public static void main(String[] args) {
        int[][] maze1 = {{1,0,0,0,0},{1,1,1,1,1},{1,0,0,0,0},{0,0,9,0,0}};
        int[][] maze2 = {{1,0,0,0,0},{1,1,1,1,1},{1,0,0,0,1},{0,0,9,1,1}};
        int[][] maze3 = {{1,1,1,1},{1,0,0,0},{1,9,0,0}};
        int[][] maze4 = {{9}};
        int[][] maze5 ={{1,1,1,1,1,1},{1,1,1,1,0,0},{0,0,1,0,0,0},{1,1,1,1,1,1},{1,0,0,0,1,0},{1,1,1,0,9,0}};

        GolfEventMaze mz = new GolfEventMaze();
        System.out.println(mz.maze(maze1, 0, 0));
        System.out.println(mz.maze(maze2, 0, 0));
        System.out.println(mz.maze(maze3, 0, 0));
        System.out.println(mz.maze(maze4, 0, 0));
        System.out.println(mz.maze(maze5, 0, 0));

        int[][] golf1 ={{1,1,0,2}, {3,1,1,1}};
        System.out.println(mz.golf(golf1, 0, 0));
    }

    public int golf(int[][] golf, int x, int y) {
        if (golf == null) return 0;
        // find all trees
        int n = golf.length;
        int m = golf[0].length;

        Map<Integer, Point> map = new TreeMap<Integer, Point>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (golf[i][j] > 1) {
                    map.put(golf[i][j], new Point(i, j, golf[i][j]));
                }
            }
        }
        Point lastpoint = null, point2;
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(0,0, golf[0][0]));
        queue.offer(new Point(0,m-1, golf[0][m-1]));
        queue.offer(new Point(n-1,0, golf[n-1][0]));
        queue.offer(new Point(n-1,m-1, golf[n-1][m-1]));

        int steps = 0;
        for (Point p : map.values()) {
            point2 = p;
            int step = bfs(golf, queue, point2);
            System.out.println(p.x + "-" + p.y + "-" + step);
            if (step == -1) return -1;
            steps += step;
            queue.clear();
            lastpoint = new Point(p.x, p.y, golf[p.x][p.y]);
            queue.offer(lastpoint);//new value
        }

        queue.clear();
        queue.offer(new Point(0,0, golf[0][0]));
        queue.offer(new Point(0,m-1, golf[0][m-1]));
        queue.offer(new Point(n-1,0, golf[n-1][0]));
        queue.offer(new Point(n-1,m-1, golf[n-1][m-1]));
        if (lastpoint != null) {
            int rest = bfs(golf, queue, lastpoint);
            if (rest > 0) {
                steps += rest;
            }
        }
        return steps;
    }

    private int bfs(int[][] matrix, Queue<Point> queue, Point target) {
        int n = matrix.length;
        int m = matrix[0].length;

        boolean[][] visited = new boolean[n][m];
        int[] gx = {0, 0, 1, -1};
        int[] gy = {1, -1, 0, 0};

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            steps++;
            for (int i = 0; i < size; i++) {
                Point p = queue.poll();
                System.out.println(":" + p.val + "x" + p.x + "y" + p.y);
                if (p.val != 1) {
                    continue;
                }

                for (int k = 0; k < 4; k++) {
                    int nx = gx[k] + p.x;
                    int ny = gy[k] + p.y;
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m ||
                            visited[nx][ny] == true) {
                        continue;
                    }
                    if (nx == target.x && ny == target.y) {
                        matrix[nx][ny] = 1;//cut the tree;
                        return steps;
                    } else if (matrix[nx][ny] != 1) {
                        continue;
                    }
                    queue.offer(new Point(nx, ny, matrix[nx][ny]));
                    visited[nx][ny] = true;
                }
            }
        }
        return -1;
    }

    public boolean maze(int[][] maze, int x, int y) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return false;
        }

        int n = maze.length;
        int m = maze[0].length;


        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(x, y, maze[x][y]));

        int[] gx = {0, 0 , 1, -1};
        int[] gy = {1,-1, 0, 0};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                Point p = queue.poll();
                if (p.val == 9) return true;
                if (p.val == 0) continue;

                for (int i = 0; i < 4; i++) {
                    int nx = gx[i] + p.x;
                    int ny = gy[i] + p.y;
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m ||
                            maze[nx][ny] <= 0) {
                        continue;
                    }
                    if (maze[nx][ny] == 9) return true;
                    queue.offer(new Point(nx, ny, maze[nx][ny]));
                    maze[nx][ny] = -1;
                }
            }
        }
        return false;
    }
}