[Swift]LeetCode1162.地图分析|AsFarfromLandasPossible

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（www.zengqiang.org）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

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

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

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

示例 1：

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

示例 2：

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

提示：

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

Runtime: 604 ms

Memory Usage: 20.9 MB

 1 class Solution {
 2     func maxDistance(_ grid: [[Int]]) -> Int {
 3         var grid = grid
 4         var has0:Bool = false
 5         var has1:Bool = false
 6         let n:Int = grid.count
 7         var x:Int = 0
 8         var y:Int = 0        
 9         var xx:Int = 0
10         var yy:Int = 0
11         var ans:Int = 1
12         var v:[[Int]] = [[1, 0],[0, 1],[-1, 0],[0, -1]]
13         var q:[[Int]] = [[Int]]()
14         for i in 0..<n
15         {
16             for j in 0..<n
17             {
18                 if grid[i][j] == 0 {has0 = true}
19                 if grid[i][j] == 1
20                 {
21                     has1 = true
22                     q.append([i,j])
23                 }
24             }
25         }
26         if !has0 {return -1}
27         if !has1 {return -1}
28         while(!q.isEmpty)
29         {
30             let arr:[Int] = q.removeFirst()
31             x = arr[0]
32             y = arr[1]
33             ans = max(ans, grid[x][y])
34             
35             for i in 0..<4
36             {
37                 xx = x + v[i][0]
38                 yy = y + v[i][1]
39                 if (xx >= 0) && (xx < n) && (yy >= 0) && (yy < n) && (grid[xx][yy] == 0)
40                 {
41                     grid[xx][yy] = grid[x][y] + 1
42                     q.append([xx, yy])
43                 }
44             }
45         }
46         return ans - 1        
47     }
48 }

652ms

 1 class Solution {
 2     
 3     typealias Location = (x: Int, y:Int)
 4     let dicts = [1, 0, -1, 0, 1]
 5     func maxDistance(_ grid: [[Int]]) -> Int {
 6         var grid = grid
 7         var queue = [Location]()
 8         
 9         for i in grid.indices {
10             for j in grid[0].indices {
11                 if grid[i][j] == 1 {
12                     queue.append(Location(x: i, y: j))
13                 }
14             }
15         }
16         
17 
18         var dist = 1
19         while queue.count > 0 {
20             
21             let size = queue.count 
22             dist += 1
23             for _ in 0..<size {
24                 let curr = queue.removeFirst()
25                 for i in 0...3 {
26                     let nextX = curr.x + dicts[i]
27                     let nextY = curr.y + dicts[i+1]
28                     guard nextX >= 0 && nextY >= 0 && nextX < grid.count && nextY < grid[0].count else {
29                         continue
30                     }
31                     
32                     if grid[nextX][nextY] == 0 {
33                         queue.append(Location(x: nextX, y: nextY))
34                         grid[nextX][nextY] = dist
35                     }
36                 }
37             }
38         }
39         
40         var result = -1 
41         for i in grid.indices {
42             for j in grid[0].indices {
43                 if grid[i][j] != 1 {
44                     result = max(result, grid[i][j] - 1)
45                 }
46             }
47         }
48         return result
49     }
50 }

740ms

 1 class Solution {
 2     func maxDistance(_ grid: [[Int]]) -> Int {
 3         // local grid to mark the visited nodes.
 4         var localGrid = grid
 5         // queue of tuples to run the BFS.
 6         var queue:[(x:Int, y:Int)] = []
 7         // find out the 1's in the grid now.
 8         let xDim = grid[0].count
 9         let yDim = grid.count
10         var water=0
11         for x in 0..<xDim {
12             for y in 0..<yDim {
13                 if grid[x][y] == 1 {
14                     queue.append((x:x, y:y))
15                 }
16                 if grid[x][y] == 0 {
17                     water += 1
18                 }
19             }
20         }
21         if water == 0 || grid.count == 0 {
22             return -1
23         }
24         var answer = 0
25         let neighborOffset:[(x:Int, y:Int)] = [(x:1,y:0),(x:-1,y:0),(x:0,y:1),(x:0,y:-1)]
26         // start BFS
27         while queue.count > 0 {
28             answer += 1
29             for i in 0..<queue.count {
30                 let current = queue.removeFirst()
31                 //print("Current (\(current.x):\(current.y))")
32                 for offset in neighborOffset {
33                     //print("Offset (\(offset.x):\(offset.y))")
34                     let xn = current.x + offset.x
35                     let yn = current.y + offset.y
36                     //print("xn \(xn) yn \(yn)")
37                     if (xn >= 0 && xn < xDim) && (yn >= 0 && yn < yDim) {
38                         if localGrid[xn][yn] == 0 {
39                             // mark it visited
40                             localGrid[xn][yn] = 1
41                             //print("(\(xn):\(yn)) = \(localGrid)")
42                             // add to explore neighbors.
43                             queue.append((x:xn, y:yn))
44                         }
45                     }
46                 }
47             }
48         }
49         return answer-1
50     }
51 }

800ms

 1 class Solution {
 2     func maxDistance(_ grid: [[Int]]) -> Int {
 3         let n = grid.count, m = grid[0].count
 4 
 5         var dp = [[Int]](repeating: [Int](repeating: -1, count: 101), count: 101)
 6 
 7         var islands = [(Int, Int)]()
 8         for i in grid.indices {
 9             for j in grid[0].indices {
10                 if grid[i][j] == 1 {
11                     islands.append((i,j))
12                     dp[i][j] = 0
13                 }
14             }
15         }
16         let dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
17         while !islands.isEmpty {
18             let front = islands.removeFirst()
19             let x = front.0, y = front.1
20             for dir in dirs {
21                 let nx = x + dir.0
22                 let ny = y + dir.1
23                 if nx < 0 || nx >= n || ny < 0 || ny >= m { continue }
24                 if dp[nx][ny] >= 0 { continue }
25                 dp[nx][ny] = dp[x][y] + 1
26                 islands.append((nx, ny))
27             }
28         }
29 
30         var ret = -1
31         for i in 0..<n {
32             for j in 0..<m where dp[i][j] > 0 {
33                 ret = max(ret, dp[i][j])
34             }
35         }
36         return ret
37     }
38 
39     func distance(_ p1: (Int, Int), _ p2: (Int, Int)) -> Int {
40         return abs(p1.0 - p2.0) + abs(p1.1 - p2.1)
41     }
42 }