网易开发笔试8.21第四题bfs

bfs,AC的,感觉类似腐烂的橘子
    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];
    }


#网易笔试##网易##笔试题目#
全部评论

相关推荐

专心打鱼:举报给她开了,正好给应届生腾一个HC
点赞 评论 收藏
分享
如题,八股刚开始学,准备好好沉淀八股,但是害怕没实习经历,简历筛选过不去,现在找实习却感觉都是已读不回,接下来该怎么安排呢?求教
Java抽象带篮子:具体背什么八股我都帮你整理好了,可以去看看我的八股专栏,这个比较详细,如果你觉得内容有点多记忆负担比较大的话,我还在更新最常问八股整理贴,是不是很贴心?
点赞 评论 收藏
分享
评论
2
7
分享
牛客网
牛客企业服务