网易开发笔试8.21第四题bfs

    int[][] d = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int minSailCost(int[][] input) {
        // write code here
        int m = input.length, n = input[0].length;
        boolean[][] is = new boolean[m][n];
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        is[0][0] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int i = poll[0], j = poll[1];
            is[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int x = i + d[k][0];
                int y = j + d[k][1];
                if (x >= 0 && x < m && y >= 0 && y < n && !is[x][y] && input[x][y] != 2) {
                    if (input[x][y] == 0) {
                        dp[x][y] = Math.min(dp[x][y], dp[i][j] + 2);
                    } else {
                        dp[x][y] = Math.min(dp[x][y], dp[i][j] + 1);
                    }
                    queue.offer(new int[]{x, y});
                }
            }
        }
        return dp[m - 1][n - 1] == Integer.MAX_VALUE ? -1 : dp[m - 1][n - 1];
    }