矩阵最长递增路径

public class Solution {
    var res = 0
    func solve ( _ matrix: [[Int]]) -> Int {        
        for i in 0..<matrix.count {
            for j in 0..<matrix[i].count {
                var arr = [Int]() //寻找到的路径
                dfs(matrix, r: i, c: j, arr: &arr)
            }
        }
        return res
    }
    
    func dfs(_ matrix: [[Int]], r: Int, c: Int, arr: inout [Int]) {
        //判断界限
        if r < 0 || r >= matrix.count || c < 0 || c >= matrix[r].count {
            res = max(res, arr.count)
            return
        }
        //如果下一个节点小于最后的数字，则可以跳过
        if let lastNum = arr.last, matrix[r][c] <= lastNum {
            res = max(res, arr.count)
            return
        }
        arr.append(matrix[r][c])
        //开始递归寻找
        dfs(matrix, r: r, c: c - 1, arr: &arr) //上
        dfs(matrix, r: r, c: c + 1, arr: &arr) //下
        dfs(matrix, r: r - 1, c: c, arr: &arr) //左
        dfs(matrix, r: r + 1, c: c, arr: &arr) //右
        arr.removeLast()
    }
}

func longestIncreasingPath(_ grid: [[Int]]) -> Int {
    guard grid.count > 0 else {
        return 0
    }
    var matrix: [[Int]] = grid
    var visitedMatrix: [[Bool]] = Array(repeating: Array(repeating: false, count: matrix[0].count), count: matrix.count)
    var result = 0
    for row in 0 ..< matrix.count {
        for col in 0 ..< matrix[0].count {
            if !visitedMatrix[row][col] {
                let lenOfPath = findIncreasingPath(&matrix, &visitedMatrix, row, col, 0)
                result = max(result, lenOfPath)
            }
        }
    }
    return result
}

// 递归查找递增的子串长度
func findIncreasingPath(_ matrix: inout [[Int]], _ visited: inout [[Bool]], _ row: Int, _ col: Int, _ curLen: Int) -> Int {
    guard row >= 0, row < matrix.count, col >= 0, col < matrix[0].count, !visited[row][col] else {
        return curLen
    }

    var lenOfPath = curLen + 1
    visited[row][col] = true // 标记该结点正在访问
    let curVal = matrix[row][col]

    // 依次向四个方向查找可以构成递增的字符串
    // 向上
    if row - 1 >= 0, matrix[row - 1][col] > curVal {
        let len = findIncreasingPath(&matrix, &visited, row - 1, col, curLen + 1)
        lenOfPath = max(len, lenOfPath)
    }

    // 向下
    if row + 1 < matrix.count, matrix[row + 1][col] > curVal {
        let len = findIncreasingPath(&matrix, &visited, row + 1, col, curLen + 1)
        lenOfPath = max(len, lenOfPath)
    }

    // 向左
    if col - 1 >= 0, matrix[row][col - 1] > curVal {
        let len = findIncreasingPath(&matrix, &visited, row, col - 1, curLen + 1)
        lenOfPath = max(len, lenOfPath)
    }

    // 向右
    if col + 1 < matrix[0].count, matrix[row][col + 1] > curVal {
        let len = findIncreasingPath(&matrix, &visited, row, col + 1, curLen + 1)
        lenOfPath = max(len, lenOfPath)
    }

    // 回溯——当前访问的节点为未访问
    visited[row][col] = false

    return lenOfPath
}