剑指offer—面试题12:矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

思考： 在矩阵中比对字符路径情况下，每次我们选对了一个字符，选择下一个字符时都面临着4中选择（如果不考虑矩阵边界的情况，上、左、右、下）。如果选择了其中一个选项，进入下一步，又面临新的选项。我们就重复选择，直到到达最终的状态。类似这种每一步所有可能选项里系统地选择一个可行的解决方案，回溯法非常适合这种多步骤的问题。

实际上回溯法类似枚举的搜索尝试过程，也就是一个个去试，我们解这道题也是通过一个个去试。

算法:

  func exist(_ board: [[Character]], _ word: String) -> Bool {
        var board = board
        
        let rows = board.count
        let columns = board.first!.count
        
        let words = Array(word)
        // 从[0][0]开始循环遍历某个点开始查找是否存在字符序列
        for i in 0..<rows {
            for j in 0..<columns {
                if hasPathCore(&board, words, i: i, j: j, index: 0) {
                    return true
                }
            }
        }
        return false
    }
    
    func hasPathCore(_ borad: inout [[Character]],_ word: [Character],i: Int, j:Int,index: Int)->Bool {
        // 如果 数据越界 或者 未找到对应的字符， index表示查找的是字符串中第几个字符
        if i<0 || i >= borad.count || j < 0 || j >= borad.first!.count || borad[i][j] != word[index] {
            return false
        }
      // 如果寻找的字符的下标等于字符串的长度-1 说明字符串已经匹配完毕。
        if index == word.count-1 {
            return true
        }
      //把当前坐标的值保存下来，为了在最后复原
        let temp = borad[i][j]
        borad[i][j] = "."
        //走递归，沿着当前坐标的上下左右4个方向查找下一个字符
        let res = hasPathCore(&borad, word, i: i+1, j: j, index: index+1) ||
        hasPathCore(&borad, word, i: i-1, j: j, index: index+1) ||
        hasPathCore(&borad, word, i: i, j: j+1, index: index+1) ||
        hasPathCore(&borad, word, i: i, j: j-1, index: index+1)
       //递归之后再把当前的坐标复原
        borad[i][j] = temp
        return res
    }