网易开发笔试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];
    }


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

相关推荐

斑驳不同:还为啥暴躁 假的不骂你骂谁啊
点赞 评论 收藏
分享
qz鹿:*** 祝他毕业就失业
点赞 评论 收藏
分享
研一开学九月份速成的Java,项目是苍穹外卖和黑马点评,算法基础不好,八股文较为熟练,想找份小厂日常实习,希望牛友们给点意见,蟹蟹啦
求offer的花生米很聪敏:三个月学了这么多?spring springmvc mybatis springboot jvm juc,还做完了两个项目,还熟悉八股,会点算法。卧槽,我该反思了。我暑假开始的,就做了外卖,spring springmvc boot 那些原理好多都忘了,还在刷 jvm 视频,八股和算法也没开始
点赞 评论 收藏
分享
评论
2
7
分享
牛客网
牛客企业服务