#P3235. 机器人活动区域(200分)
-
1000ms
Tried: 69
Accepted: 29
Difficulty: 3
所属公司 :
华为od
机器人活动区域(200分)
题目描述
给定一个大小为 M×N 的网格,每个网格包含一个非负整数编号(0≤k≤50)。机器人可以从任意位置开始,且只能在相邻网格(上下左右)间移动。当相邻网格的数字编号差值的绝对值小于等于 1 时,机器人可以在网格间移动。
求机器人可活动的最大范围对应的网格点数目,即满足移动条件的最大连通区域的大小。
思路
这是一个典型的网格中的连通区域问题。我们需要找到满足特定条件的最大连通区域的大小。
具体步骤:
-
遍历网格: 对于每一个未被访问过的网格点,进行搜索。
-
深度优先搜索(DFS)或广度优先搜索(BFS): 从当前网格点出发,搜索所有满足条件的相邻网格。
- 移动条件: 当前网格点与相邻网格点的数字编号差值的绝对值小于等于 1。
-
记录区域大小: 在搜索过程中,统计连通区域的大小。
-
更新最大值: 比较并更新最大连通区域的大小。
-
重复步骤1-4: 直到所有的网格点都被访问过。
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int dx[4] = {0, 0, -1, 1}; // 上下左右移动
const int dy[4] = {-1, 1, 0, 0};
int M, N;
vector<vector<int>> grid;
vector<vector<bool>> visited;
int dfs(int x, int y) {
visited[x][y] = true;
int count = 1; // 当前网格点计数为1
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// 检查边界
if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
// 检查是否已访问以及数字差值条件
if (!visited[nx][ny] && abs(grid[x][y] - grid[nx][ny]) <= 1) {
count += dfs(nx, ny);
}
}
}
return count;
}
int main() {
cin >> M >> N;
grid.resize(M, vector<int>(N));
visited.resize(M, vector<bool>(N, false));
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
cin >> grid[i][j];
int max_area = 0;
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
if (!visited[i][j]) {
int area = dfs(i, j);
max_area = max(max_area, area);
}
cout << max_area << endl;
return 0;
}
python
M, N = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(M)]
visited = [[False]*N for _ in range(M)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def dfs(x, y):
visited[x][y] = True
count = 1
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < M and 0 <= ny < N:
if not visited[nx][ny] and abs(grid[x][y] - grid[nx][ny]) <= 1:
count += dfs(nx, ny)
return count
max_area = 0
for i in range(M):
for j in range(N):
if not visited[i][j]:
area = dfs(i, j)
max_area = max(max_area, area)
print(max_area)
java
import java.util.Scanner;
public class Main {
static int M, N;
static int[][] grid;
static boolean[][] visited;
static int[] dx = {0, 0, -1, 1}; // 上下左右
static int[] dy = {-1, 1, 0, 0};
static int dfs(int x, int y) {
visited[x][y] = true;
int count = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
if (!visited[nx][ny] && Math.abs(grid[x][y] - grid[nx][ny]) <= 1) {
count += dfs(nx, ny);
}
}
}
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
grid = new int[M][N];
visited = new boolean[M][N];
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
grid[i][j] = sc.nextInt();
int max_area = 0;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
if (!visited[i][j]) {
int area = dfs(i, j);
max_area = Math.max(max_area, area);
}
System.out.println(max_area);
}
}
题目内容
现有一个机器人,可放置于 M×N 的网格中任意位置,每个网格包含一个非负整数编号,当相邻网格的数字编号差值的绝对值小于等于 1 时,机器人可以在网格间移动。
问题: 求机器人可活动的最大范围对应的网格点数目。
说明:
- 网格左上角坐标为 (0,0) ,右下角坐标为 (m−1,n−1)
- 机器人只能在相邻网格间上下左右移动
示例1 输入如下网格

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

输出:1
说明:任意两个相邻网格的差值绝对值都大于 1,机器人不能在网格间移动,只能在单个网格内活动,对应网格点数目为 1
输入描述
第 1 行输入为 M 和 N
- 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