题目描述：

现有一个机器人，可放置于 M × N 的网格中任意位置，每个网格包含一个非负整数编号。当相邻网格的数字编号差值的绝对值小于等于 1 时，机器人可在网格间移动

问题：求机器人可活动的最大范围对应的网格点数目。

说明：

1）网格左上角坐标为 (0, 0)，右下角坐标为 (m-1, n-1)

2）机器人只能在相邻网格间上、下、左、右移动

示例1

输入

4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4

输出：

6

说明：图中绿色区域，相邻网格差值绝对值都小于等于1，且为最大区域，对应网格点数目为6

示例2

输入

2 3 1 3 5 4 1 3

输出：

1

说明：任意两个相邻网格的差值绝对值都大于1，机器人不能在网格间移动，只能在单个网格内活动，对应网格点数目为 1

题解

这道题目本质上是一个图的连通性问题。

可以将网格看作一个图，每个格子是一个节点，相邻且差值不超过 1 的格子之间有一条边。问题就转化为找到最大的连通分量。

解决这个问题的一个有效方法是使用深度优先搜索（DFS）或广度优先搜索（BFS）或者 并查集（DSU）。

这里以 DFS 为例来解释解题思路：

遍历整个网格，对每个未访问的格子进行 DFS。

在 DFS 过程中，检查当前格子的上下左右四个相邻格子。

如果相邻格子未访问过，且与当前格子的差值绝对值不超过 1，则继续对该相邻格子进行 DFS。

实现时，可以使用一个二维数组来存储网格数据，另一个二维数组来标记已访问的格子。

源码

public class RobotLiveArea {

	static Input input ;
	static {
		input = new Input("4 4\n" +
				"1 2 5 2\n" +
				"2 4 4 5\n" +
				"3 5 7 1\n" +
				"4 6 2 4");
	}
	static  int[][] area;
	static int m, n;
	static boolean[][] visited;

	public static void main(String[] args) {
		String[] str = input.nextLine().split(" ");

		m = Integer.parseInt(str[0]);
		n = Integer.parseInt(str[1]);
		area = new int[m][n];
		visited = new boolean[m][n];

		for (int i = 0; i < m; i++) {
			String[] ss = input.nextLine().split(" ");
			for (int j = 0; j < n; j++) {
				area[i][j] = Integer.parseInt(ss[j]);
			}
		}

		int result = 1;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				result = Math.max(dfs(i, j), result);
			}
		}

		System.out.println(result);
	}

	public static int dfs(int x, int y) {
		if (isOverBound(x, y)) {
			return 0;
		}
		if (visited[x][y]) {
			return 0;
		}
		visited[x][y] = true;

		int result = 1;
		int[][] direction = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
		for (int i = 0; i < direction.length; i++) {
			int newX = x + direction[i][0];
			int newY = y + direction[i][1];
			if (!isOverBound(newX, newY) // 下一个坐标没有越界
					&& !visited[newX][newY]  // 下一个坐标没有被访问过
					&& Math.abs(area[newX][newY] - area[x][y]) <= 1) { // 下一个高度差不是过大
				result += dfs(newX, newY);
			}
		}
		return result;
	}

	public static boolean isOverBound(int x, int y) {
		if (x >= m || y >= n || x < 0 || y < 0) {
			return true;
		}
		return false;
	}

}