AcWing 901. 滑雪---Java
原题链接
简单
作者:
夏日的小提琴
,
2021-12-06 11:20:33
,
所有人可见
,
阅读 184
import java.io.*;
public class Main {
static int n, m;
static int[][] h;
static int[][] f;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] str = reader.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
h = new int[n + 1][m + 1];
f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
String[] str1 = reader.readLine().split(" ");
for (int j = 1; j <= m; j++) {
h[i][j] = Integer.parseInt(str1[j - 1]);
f[i][j] = -1;//初始化为-1,表示每个状态没被算过
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
res = Math.max(res, dfs(i, j));//遍历每个初始点,dfs用于求出从该初始点出发所能经过的最大长度
}
}
writer.write(res + "");
writer.flush();
writer.close();
reader.close();
}
public static int dfs(int x, int y) {
if (f[x][y] != -1) return f[x][y];//如果该点的最大的路径长度之前已经算出,则直接返回,不用再计算
f[x][y] = 1;//表示f[x][y]的最小值为1,表示走当前该点
for (int i = 0; i < 4; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]) {
f[x][y] = Math.max(f[x][y], dfs(a, b) + 1);//取四个方向中可走路线的最大长度
}
}
return f[x][y];
}
}