主体思路
状态表示:dp[i][j]
表示从坐标(i, j)开始滑的距离
状态转移方程: dp[i][j] = max(dp[i][j], dfs(nx, ny) + 1)
需要用递归函数dfs和四方向数组不断搜索整个滑雪场
注意细节
题目给的数据是有点大,可以考虑使用 bufio + os
快读
基础代码
package main
import "fmt"
var (
R, C int
g, dp [][]int
dx = [4]int{-1, 0, 1, 0}
dy = [4]int{0, 1, 0, -1}
)
func max(i, j int) int { if i > j { return i }; return j }
func dfs(x, y int) int {
if dp[x][y] != -1 { return dp[x][y] }
dp[x][y] = 1
for i := 0; i < 4; i++ {
nx := x + dx[i]
ny := y + dy[i]
if nx >= 1 && nx <= R && ny >= 1 && ny <= C && g[x][y] > g[nx][ny] { dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)}
}
return dp[x][y]
}
func main() {
fmt.Scanf("%d%d", &R, &C)
g, dp = make([][]int, R + 1), make([][]int, R + 1)
for i := 0; i <= R; i++ {
g[i] = make([]int, C + 1)
dp[i] = make([]int, C + 1)
for j := 0; j <= C; j++ { dp[i][j] = -1 }
}
for i := 1; i <= R; i++ {
for j := 1; j <= C; j++ { fmt.Scanf("%d", &g[i][j]) }
}
res := 0
for i := 1; i <= R; i++ {
for j := 1; j <= C; j++ { res = max(res, dfs(i, j)) }
}
fmt.Println(res)
}
使用bufio + os 快读
效果还是很显著的,上面的是bufio + os, 下面的是fmt
package main
import (
"bufio"
"os"
"fmt"
)
var (
R, C int
g, dp [][]int
dx = [4]int{-1, 0, 1, 0}
dy = [4]int{0, 1, 0, -1}
in = bufio.NewReader(os.Stdin)
)
func max(i, j int) int { if i > j { return i }; return j }
func dfs(x, y int) int {
if dp[x][y] != -1 { return dp[x][y] }
dp[x][y] = 1
for i := 0; i < 4; i++ {
nx := x + dx[i]
ny := y + dy[i]
if nx >= 1 && nx <= R && ny >= 1 && ny <= C && g[x][y] > g[nx][ny] { dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)}
}
return dp[x][y]
}
func main() {
fmt.Fscan(in, &R, &C)
g, dp = make([][]int, R + 1), make([][]int, R + 1)
for i := 0; i <= R; i++ {
g[i] = make([]int, C + 1)
dp[i] = make([]int, C + 1)
for j := 0; j <= C; j++ { dp[i][j] = -1 }
}
for i := 1; i <= R; i++ {
for j := 1; j <= C; j++ { fmt.Fscan(in, &g[i][j]) }
}
res := 0
for i := 1; i <= R; i++ {
for j := 1; j <= C; j++ { res = max(res, dfs(i, j)) }
}
fmt.Println(res)
}