题解 | #矩阵最长递增路径#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
*/
func solve( matrix [][]int ) int {
    result:=make([]int,0)
    visit:=make([][]bool,len(matrix))
    for i:=range visit{
        visit[i]=make([]bool,len(matrix[0]))
    }
    for i:=0;i<len(matrix);i++{
        for j:=0;j<len(matrix[0]);j++{
            dfs(i,j,visit,0,matrix,&result)
        }
    }
    
    max:=0
    for _,v:=range result{
        if v>max{
            max=v
        }
    }
    return max
}

func dfs(x,y int,visit [][]bool,path int,matrix [][]int,result *[]int){
    if visit[x][y]==true{
        *result=append(*result, path)
        return
    }
    path++
    visit[x][y]=true
    isMax:=true
    if x-1>=0&&matrix[x-1][y]>matrix[x][y]{
        dfs(x-1, y, visit, path, matrix, result)
        isMax=false
    }
    if y-1>=0&&matrix[x][y-1]>matrix[x][y]{
        dfs(x, y-1, visit, path, matrix, result)
        isMax=false
    }
    if x+1<len(matrix)&&matrix[x+1][y]>matrix[x][y]{
        dfs(x+1, y, visit, path, matrix, result)
        isMax=false
    }
    if y+1<len(matrix[0])&&matrix[x][y+1]>matrix[x][y]{
        dfs(x, y+1, visit, path, matrix, result)
        isMax=false
    }
    if isMax{
        *result=append(*result, path)
    }
    visit[x][y]=false
    path--
}