[Swift]LeetCode909.蛇梯棋|SnakesandLadders

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

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

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

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

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

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

On an N x N board, the numbers from 1 to N*N are written boustrophedonically starting from the bottom left of the board, and alternating direction each row. For example, for a 6 x 6 board, the numbers are written as follows:

You start on square 1 of the board (which is always in the last row and first column). Each move, starting from square x, consists of the following:

You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N.
- (This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations.)
If S has a snake or ladder, you move to the destination of that snake or ladder. Otherwise, you move to S.

A board square on row r and column c has a "snake or ladder" if board[r][c] != -1. The destination of that snake or ladder is board[r][c].

Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving. (For example, if the board is `[[4,-1],[-1,3]]`, and on the first move your destination square is `2`, then you finish your first move at `3`, because you do not continue moving to `4`.)

Return the least number of moves required to reach square N*N. If it is not possible, return -1.

Example 1:

Input: [
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
At the beginning, you start at square 1 [at row 5, column 0].
You decide to move to square 2, and must take the ladder to square 15.
You then decide to move to square 17 (row 3, column 5), and must take the snake to square 13.
You then decide to move to square 14, and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
It can be shown that you need at least 4 moves to reach the N*N-th square, so the answer is 4.

Note:

2 <= board.length = board[0].length <= 20
board[i][j] is between 1 and N*N or is equal to -1.
The board square with number 1 has no snake or ladder.
The board square with number N*N has no snake or ladder.

在一块 N x N 的棋盘 board 上，从棋盘的左下角开始，每一行交替方向，按从 1 到 N*N 的数字给方格编号。例如，对于一块 6 x 6 大小的棋盘，可以编号如下：

玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。

每一次从方格 x 起始的移动都由以下部分组成：

你选择一个目标方块 S，它的编号是 x+1，x+2，x+3，x+4，x+5，或者 x+6，只要这个数字 <= N*N。
如果 S 有一个蛇或梯@@子，你就移动到那个蛇或梯@@子的目的地。否则，你会移动到 S。

在 r 行 c 列上的方格里有 “蛇” 或 “ 梯@@子 ”；如果 board[r][c] != -1，那个蛇或梯@@子的目的地将会是 board[r][c]。

注意，你每次移动最多只能爬过蛇或梯@@子一次：就算目的地是另一条蛇或梯@@子的起点，你也不会继续移动。

返回达到方格 N*N 所需的最少移动次数，如果不可能，则返回 -1。

示例：

输入：[
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
输出：4
解释：
首先，从方格 1 [第 5 行，第 0 列] 开始。
你决定移动到方格 2，并必须爬过 梯@@子 移动到到方格 15。
然后你决定移动到方格 17 [第 3 行，第 5 列]，必须爬过蛇到方格 13。
然后你决定移动到方格 14，且必须通过 梯@@子 移动到方格 35。
然后你决定移动到方格 36, 游戏结束。
可以证明你需要至少 4 次移动才能到达第 N*N 个方格，所以答案是 4。

提示：

2 <= board.length = board[0].length <= 20
board[i][j] 介于 1 和 N*N 之间或者等于 -1。
编号为 1 的方格上没有蛇或梯@@子。
编号为 N*N 的方格上没有蛇或梯@@子。

Runtime: 84 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func snakesAndLadders(_ board: [[Int]]) -> Int {
 3         var n:Int = board.count
 4         var arr:[Int] = [Int](repeating:0,count:n * n)
 5         var i:Int = n - 1
 6         var j:Int = 0
 7         var index:Int = 0
 8         var inc:Int = 1
 9         while (index < n * n)
10         {
11             arr[index] = board[i][j]
12             index += 1
13             if inc == 1 && j == n - 1
14             {
15                 inc = -1
16                 i -= 1
17             }
18             else if inc == -1 && j == 0
19             {
20                 inc = 1
21                 i -= 1
22             }
23             else
24             {
25                 j += inc
26             }
27         }
28         var visited:[Bool] = [Bool](repeating:false,count:n * n)
29         var q:[Int] = [Int]()
30         var start:Int = arr[0] > -1 ? arr[0] - 1 : 0
31         q.append(start)
32         visited[start] = true
33         var step:Int = 0
34         while (!q.isEmpty)
35         {
36             var size:Int = q.count
37             while(size > 0)
38             {
39                 var cur:Int = q.removeFirst()
40                 if cur == n * n - 1
41                 {
42                     return step
43                 }
44                 var next:Int = cur + 1
45                 while(next <= min(cur + 6, n * n - 1))
46                 {
47                     var dest:Int = arr[next] > -1 ? arr[next] - 1 : next
48                     if !visited[dest]
49                     {
50                         visited[dest] = true
51                         q.append(dest)
52                     }
53                     next += 1
54                 }
55                 size -= 1
56             } 
57             step += 1
58         }
59         return -1
60     }
61 }

96ms

 1 class Solution {
 2     func snakesAndLadders(_ board: [[Int]]) -> Int {
 3         var flatBoard = [Int]()
 4         let n = board.count
 5         var fromLeft = true
 6         for row in board.reversed() {
 7             if fromLeft {
 8                 fromLeft = false
 9                 for x in row {
10                     flatBoard.append(x)
11                 }
12             } else {
13                 fromLeft = true
14                 for x in row.reversed() {
15                     flatBoard.append(x)
16                 }
17             }
18         }
19         flatBoard.insert(0, at: 0)
20         var queue = [Int]()
21         queue.append(1)
22         var counter = [Int](repeating:-1, count: n*n + 1)
23         counter[1] = 0
24         while queue.count > 0 {
25             let curr = queue.removeLast()
26             
27             for i in 1...6 {
28                 var next = curr + i
29                 if next > n*n {
30                     break
31                 }
32                 if flatBoard[next] != -1 {
33                     next = flatBoard[next]
34                 }
35                 if next == n*n {
36                     return counter[curr] + 1
37                 }
38                 if counter[next] == -1 {
39                     queue.insert(next, at: 0)
40                     counter[next] = counter[curr] + 1
41                 }
42             }
43         }        
44         return -1
45     }
46 }

104ms

 1 class Solution {
 2     func snakesAndLadders(_ board: [[Int]]) -> Int {
 3         var newBoard: [Int] = []                
 4         var movingForward = true
 5         for i in (0..<board.count).reversed() {
 6             newBoard += movingForward ? board[i] : Array(board[i].reversed())
 7             movingForward = !movingForward
 8         }
 9         
10         var steps = 0
11         var queue: [Int] = [0]
12         var visited: [Bool] = Array(repeating: false, count: newBoard.count)
13         visited[0] = true                
14         
15         while(!queue.isEmpty) {
16             var size = queue.count
17             while (size > 0) {
18                 let curr = queue.removeFirst()            
19                 if curr >= newBoard.count - 1 {                     
20                     return steps
21                 }        
22 
23                 let range = curr + 1...min(curr + 6, newBoard.count - 1)              
24                 for j in range { 
25                     let dest = newBoard[j] > -1 ? newBoard[j] - 1 : j
26                     if !visited[dest] {  
27                         visited[dest] = true
28                         queue.append(dest) 
29                     }
30                 }                
31                 size -= 1
32             }
33             steps += 1            
34         }        
35         return -1
36     }
37 }