题目描述
给定一个大小为 M×N 的网格,每个网格包含一个非负整数编号(0≤k≤50)。机器人可以从任意位置开始,且只能在相邻网格(上下左右)间移动。当相邻网格的数字编号差值的绝对值小于等于 1 时,机器人可以在网格间移动。
求机器人可活动的最大范围对应的网格点数目,即满足移动条件的最大连通区域的大小。
思路
这是一个典型的网格中的连通区域问题。我们需要找到满足特定条件的最大连通区域的大小。
P3235.机器人活动区域(200分)
题目内容
现有一个机器人,可放置于 M×N 的网格中任意位置,每个网格包含一个非负整数编号,当相邻网格的数字编号差值的绝对值小于等于 1 时,机器人可以在网格间移动。
问题: 求机器人可活动的最大范围对应的网格点数目。
说明:
- 网格左上角坐标为 (0,0) ,右下角坐标为 (m−1,n−1)
- 机器人只能在相邻网格间上下左右移动
示例1 输入如下网格

输出:6
说明:图中绿色区域,相邻网格差值绝对值都小于等于 1 ,且为最大区域,对应网格点数目为 6
示例2 输入如下网格

输出:1
说明:任意两个相邻网格的差值绝对值都大于 1,机器人不能在网格间移动,只能在单个网格内活动,对应网格点数目为 1
输入描述
第 1 行输入为 M 和 N
之后 M 行表示网格数值,每行 N 个数值(数值大小用 k 表示),数值间用单个空格分隔,行首行尾无多余空格。
- M、N、k 均为整数
- 1≤M,N≤150
- 0≤k≤50
输出描述
输出 1 行,包含 1 个数字,表示最大活动区域的网格点数目,
行首行尾无多余空格。
样例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
说明
见题目内容中示例 2,最大区域对应网格点数目为 1