[Swift]LeetCode1102.得分最高的路径|PathWithMaximumMinimumValue

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

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

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

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

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

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

Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].

The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.

A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).

Example 1:

Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: 
The path with the maximum score is highlighted in yellow.

Example 2:

Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2

Example 3:

Input: [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3

Note:

1 <= R, C <= 100
0 <= A[i][j] <= 10^9

给你一个 R 行 C 列的整数矩阵 A。矩阵上的路径从 [0,0] 开始，在 [R-1,C-1] 结束。

路径沿四个基本方向（上、下、左、右）展开，从一个已访问单元格移动到任一相邻的未访问单元格。

路径的得分是该路径上的最小值。例如，路径 8 → 4 → 5 → 9 的值为 4 。

找出所有路径中得分最高的那条路径，返回其得分。

示例 1：

输入：[[5,4,5],[1,2,6],[7,4,6]]
输出：4
解释： 
得分最高的路径用黄色突出显示。

示例 2：

输入：[[2,2,1,2,2,2],[1,2,2,2,1,2]]
输出：2

示例 3：

输入：[[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
输出：3

提示：

1 <= R, C <= 100
0 <= A[i][j] <= 10^9

 1 class Solution {
 2     let dir:[[Int]] = [[0,1],[0,-1],[1,0],[-1,0]]
 3     func maximumMinimumPath(_ A: [[Int]]) -> Int {
 4         var A = A
 5         let n:Int = A.count
 6         let m:Int = A[0].count
 7         var l:Int = 0
 8         var r:Int = min(A[0][0], A[n-1][m-1])
 9         while (l < r)
10         {
11             let mid:Int = l + ((r-l)>>1) + 1
12             if check(mid, n, m, &A)
13             {
14                 l = mid
15             }
16             else
17             {
18                 r = mid - 1
19             }
20         }
21         return l
22     }
23     
24     func check(_ lim:Int,_ n:Int,_ m:Int,_ a:inout [[Int]]) ->Bool
25     {
26         var vis:[[Bool]] = [[Bool]](repeating:[Bool](repeating:false,count:m),count:n)
27         vis[0][0] = true
28         var qu:[[Int]] = [[Int]]()
29         qu.append([0,0])
30         while(!qu.isEmpty)
31         {
32             let arr:[Int] = qu.removeFirst()
33             let x:Int = arr[0]
34             let y:Int = arr[1]
35             
36             
37             for i in 0..<4
38             {
39                 let tx:Int = x + dir[i][0]
40                 let ty:Int = y + dir[i][1]
41                 if tx < 0 || tx >= n || ty < 0 || ty >= m || vis[tx][ty] || a[tx][ty] < lim
42                 {
43                     continue
44                 }
45                 if tx == n-1 && ty == m-1
46                 {
47                     return true
48                 }
49                 qu.append([tx, ty])
50                 vis[tx][ty] = true
51             }
52         }
53         return false
54     }
55 }