解题思路:dfs搜索,笨办法。for循环二维数组,从每个点出发,把每个点能走到的距离记录到一个list里,最后对这个list进行求最大值即可。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class OJTest11 {
static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//移动的四个方向,上下左右
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int M = in.nextInt();
int N = in.nextInt();
int[][] maze = new int[M][N];
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[0].length; j++) {
maze[i][j] = in.nextInt();
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[0].length; j++) {
int rs = solveMachine(maze, i, j);
result.add(rs);
}
}
System.out.println(result.stream().max(Integer::compareTo).orElse(null));
}
private static int solveMachine(int[][] maze, int i, int j) {
//定义一个boolean的二维数组来记录路径是否走过了,走过了标记为true
int M = maze.length;
int N = maze[0].length;
int count =0;
boolean[][] visited = new boolean[M][N];
if (!dfs(maze, i, j, visited)) {
for (boolean[] bs : visited) {
for (boolean b : bs) {
if (b) {
count++;
}
}
}
}
return count;
}
public static boolean dfs(int[][] maze, int i, int j, boolean[][] visited) {
visited[i][j] = true; //进来函数先标记当前点
//递归中止条件,发现上下左右都不能走就是中止条件
for (int[] dir : directions) {
int newX = i + dir[0];
int newY = j + dir[1];
if (newX >= 0 && newX < maze.length && newY >= 0 && newY < maze[0].length && !visited[newX][newY]) {
if (Math.abs(maze[i][j] - maze[newX][newY]) <= 1) {
dfs(maze, newX, newY, visited);
}
}
}
//走到这说明四个方向都尝试了走不通,直接返回上层即可
return false;
}
}