题解 | #滑雪#

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var arr [][]int
var dp [][]int

func solution(arr [][]int) int {
	dp = make([][]int, len(arr))
	for i := 0; i < len(dp); i++ {
		tmp := make([]int, len(arr[0]))
		for j := 0; j < len(tmp); j++ {
			tmp[j] = 1
		}
		dp[i] = tmp
	}
	//上下左右遍历
	res := 0
	totalRow, totalCol := len(arr), len(arr[0])
	for i := 0; i < totalRow; i++ {
		for j := 0; j < totalCol; j++ {
			dfs(totalRow, totalCol, i, j)
			res = max(res, dp[i][j])
		}
	}
	return res
}

func dfs(totalRow, totalCol, posRow, posCol int) {
	//上
	if (posRow-1 >= 0) && (arr[posRow-1][posCol] < arr[posRow][posCol]) {
		dfs(totalRow, totalCol, posRow-1, posCol)
		dp[posRow][posCol] = max(dp[posRow][posCol], dp[posRow-1][posCol]+1)
	}
	//下
	if (posRow+1 < totalRow) && (arr[posRow+1][posCol] < arr[posRow][posCol]) {
		dfs(totalRow, totalCol, posRow+1, posCol)
		dp[posRow][posCol] = max(dp[posRow][posCol], dp[posRow+1][posCol]+1)
	}
	//左
	if (posCol-1 >= 0) && (arr[posRow][posCol-1] < arr[posRow][posCol]) {
		dfs(totalRow, totalCol, posRow, posCol-1)
		dp[posRow][posCol] = max(dp[posRow][posCol], dp[posRow][posCol-1]+1)
	}
	//右
	if (posCol+1 < totalCol) && (arr[posRow][posCol+1] < arr[posRow][posCol]) {
		dfs(totalRow, totalCol, posRow, posCol+1)
		dp[posRow][posCol] = max(dp[posRow][posCol], dp[posRow][posCol+1]+1)
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
*
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
结果
25
*/
func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	str := scanner.Text()
	strs := strings.Split(str, " ")
	row, _ := strconv.Atoi(strs[0])

	arr = make([][]int, row)
	for i := 0; i < row; i++ {
		scanner.Scan()
		str = scanner.Text()
		strs = strings.Split(str, " ")
		tmp := make([]int, 0)
		for _, val := range strs {
			ele, _ := strconv.Atoi(val)
            tmp = append(tmp, ele)
		}
		arr[i] = tmp
	}
	fmt.Println(solution(arr))
}