leetcode1162-地图分析

原题

你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋,请返回 -1

示例 1:

leetcode1162-地图分析

输入: [[1,0,1],[0,0,0],[1,0,1]] 输出: 2
解释:
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。

示例 2:

leetcode1162-地图分析

输入: [[1,0,0],[0,0,0],[0,0,0]] 输出: 4
解释:
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大,最大距离为 4。

提示:

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[i][j] 不是 0 就是 1

解法

思想

左上,右下两遍动态规划。

时间复杂度:O(4*N^2) = O(N^2)

代码

class Solution {
    public int maxDistance(int[][] grid) {
        int [][]dp=new int [grid.length][grid[0].length];
        int i,j;
        int ans=0;
        for(i=0;i<grid.length;i++)
            for(j=0;j<grid.length;j++)
                dp[i][j]=200;

        for(i=0;i<grid.length;i++)
            for(j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]==1)
                    dp[i][j]=0;
                if(i<grid.length-1)
                    dp[i+1][j]=Math.min(dp[i][j]+1,dp[i+1][j]);
                if(j<grid[0].length-1)
                    dp[i][j+1]=Math.min(dp[i][j]+1,dp[i][j+1]);
            }

        for(i=grid.length-1;i>=0;i--)
            for(j=grid[0].length-1;j>=0;j--)
            {
                if(i>=1)
                    dp[i-1][j]=Math.min(dp[i-1][j],dp[i][j]+1);
                if(j>=1)
                    dp[i][j-1]=Math.min(dp[i][j]+1,dp[i][j-1]);
            }

        for(i=0;i<grid.length;i++)
            for(j=0;j<grid[0].length;j++)
                ans=Math.max(ans,dp[i][j]);

        if(ans==0||ans==200)
            return -1;
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1162-%e5%9c%b0%e5%9b%be%e5%88%86%e6%9e%90/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月29日 00:13
下一篇 2020年3月29日 12:37

相关推荐

  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

    2020年1月24日
    0200
  • leetcode836-矩形重叠

    原题 矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。 如果相交的面积为正,则称两矩形重叠。需要…

    算法 2020年3月18日
    0450
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0400
  • leetcode24-两两交换链表中的节点

    原题 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例: 给定 1->2->3->…

    算法 2020年1月20日
    0200
  • leetcode55-跳跃游戏

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入: [2,3,1…

    算法 2020年2月9日
    080
  • leetcode752-打开转盘锁

    原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由…

    2019年12月9日
    0290
  • leetcode343-整数拆分

    原题 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1…

    算法 2020年4月13日
    0110
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    080
  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0130
  • leetcode235-二叉搜索树的最近公共祖先

    原题 给定一个二叉二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x …

    2020年1月17日
    0100

发表回复

登录后才能评论