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

相关推荐

  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

    算法 2020年5月4日
    070
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0110
  • leetcode56-合并区间

    原题 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]…

    算法 2020年4月16日
    0160
  • leetcode75-颜色分类

    原题 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分…

    算法 2020年4月19日
    0220
  • leetcode86-分隔链表

    原题 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head…

    算法 2020年4月27日
    0140
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0110
  • leetcode279-完全平方数

    原题 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出…

    2019年12月11日
    0120
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0240
  • leetcode210-课程表II

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

    算法 2020年5月17日
    0120
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    080

发表回复

登录后才能评论