华为OD机试 - 可活动的最大网格点数目 - 广度优先搜索BFS（Python/JS/C/C++ 2024 E卷 200分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

问题：求机器人可活动的最大范围对应的网格点数量。
说明：网格左上角坐标为(0,0)，右下角坐标为(M-1,N-1)，机器人只能在相邻网格间上下左右移动。

二、输入描述

第 1 行输入 M 和 N，M 表示网格的行数 N 表示网格的列数
之后 M 行表示网格数组，每行 N 个数值（数值为 0 到 5 之间），数值间用单个空格分隔，行与行无多余空格。

M、N、K 均为整数，且 1 ≤ M, N ≤ 150, 0 ≤ K ≤ 50

三、输出描述

输出 1 行，包含 1 个数字，表示最大活动区域的网格点数目，行首行尾无多余空格。

四、测试用例

测试用例1：

1、输入

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

2、输出

3、说明

相邻网格差值的绝对值都小于等于 1，且为最大区域，对应网格点数目为 6。

测试用例2：

1、输入

3 3
0 1 0
1 2 1
0 1 0

2、输出

3、说明

所有网格点的编号差的绝对值都不超过 1，整个网格都是一个连通区域，包含 9 个网格点。

五、解题思路

1、问题理解

给定一个 M × N 的网格，网格中的每个点有一个非负整数编号（0 到 5）。机器人可以在网格中任意放置起始点，然后在相邻的上下左右网格间移动，移动的条件是相邻网格编号的差的绝对值不超过 1。要求求出机器人在网格中可活动的最大范围，即能够到达的网格点的最大数量。

2、解决方案

为了求解这个问题，我们需要找到网格中最大的连通区域，其中相邻网格之间的编号差的绝对值不超过 1。这个问题可以转化为在图中寻找最大连通分量的问题，其中每个网格点是图中的一个节点，相邻的节点之间有边连接，前提是它们的编号差的绝对值不超过 1。

遍历网格中的每一个未被访问的点，使用 BFS 来找到与之相连的所有符合条件的点，记录下连通区域的大小，并更新最大连通区域的大小。

六、Python算法源码

# Python版本
import sys
from collections import dequedef main():# 读取所有输入input = sys.stdin.read().split()idx = 0# 读取网格的行数M和列数NM = int(input[idx])N = int(input[idx + 1])idx += 2# 初始化网格数组grid = []for _ in range(M):row = []for _ in range(N):row.append(int(input[idx]))idx += 1grid.append(row)# 初始化访问标记数组，全部设置为Falsevisited = [[False for _ in range(N)] for _ in range(M)]max_region = 0  # 记录最大连通区域的大小# 定义四个方向的移动：上、下、左、右directions = [(-1,0), (1,0), (0,-1), (0,1)]# 遍历每一个网格点for i in range(M):for j in range(N):if not visited[i][j]:# 使用BFS计算当前连通区域的大小queue = deque()queue.append((i,j))visited[i][j] = Truecount = 1while queue:x, y = queue.popleft()for dx, dy in directions:new_x = x + dxnew_y = y + dy# 判断新位置是否在网格范围内且未被访问if 0 <= new_x < M and 0 <= new_y < N and not visited[new_x][new_y]:# 判断编号差的绝对值是否小于等于1if abs(grid[x][y] - grid[new_x][new_y]) <= 1:queue.append((new_x, new_y))visited[new_x][new_y] = Truecount += 1# 更新最大连通区域的大小if count > max_region:max_region = count# 输出结果print(max_region)if __name__ == "__main__":main()

七、JavaScript算法源码

// JavaScript版本
const readline = require('readline');// 创建接口以逐行读取输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];
rl.on('line', function(line){input = input.concat(line.trim().split(' '));
}).on('close', function(){let idx = 0;// 读取网格的行数M和列数Nconst M = parseInt(input[idx++]);const N = parseInt(input[idx++]);// 初始化网格数组let grid = [];for(let i = 0; i < M; i++){let row = [];for(let j = 0; j < N; j++){row.push(parseInt(input[idx++]));}grid.push(row);}// 初始化访问标记数组，全部设置为falselet visited = Array.from({length: M}, () => Array(N).fill(false));let maxRegion = 0; // 记录最大连通区域的大小// 定义四个方向的移动：上、下、左、右const directions = [[-1, 0],[1, 0],[0, -1],[0, 1]];// 遍历每一个网格点for(let i = 0; i < M; i++){for(let j = 0; j < N; j++){if(!visited[i][j]){// 使用BFS计算当前连通区域的大小let queue = [];queue.push([i, j]);visited[i][j] = true;let count = 1;while(queue.length > 0){let [x, y] = queue.shift();for(let dir = 0; dir < directions.length; dir++){let newX = x + directions[dir][0];let newY = y + directions[dir][1];// 判断新位置是否在网格范围内且未被访问if(newX >=0 && newX < M && newY >=0 && newY < N && !visited[newX][newY]){// 判断编号差的绝对值是否小于等于1if(Math.abs(grid[x][y] - grid[newX][newY]) <= 1){queue.push([newX, newY]);visited[newX][newY] = true;count++;}}}}// 更新最大连通区域的大小if(count > maxRegion){maxRegion = count;}}}}// 输出结果console.log(maxRegion);
});

八、C算法源码

/* C语言版本 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 定义队列结构
typedef struct {int x;int y;
} Point;// 定义队列大小
typedef struct {Point *data;int front;int rear;int size;
} Queue;// 初始化队列
Queue* createQueue(int max_size){Queue *q = (Queue*)malloc(sizeof(Queue));q->data = (Point*)malloc(sizeof(Point)*max_size);q->front = 0;q->rear = 0;q->size = max_size;return q;
}// 判断队列是否为空
bool isEmpty(Queue *q){return q->front == q->rear;
}// 入队
void enqueue(Queue *q, int x, int y){q->data[q->rear].x = x;q->data[q->rear].y = y;q->rear = (q->rear + 1) % q->size;
}// 出队
Point dequeue(Queue *q){Point p = q->data[q->front];q->front = (q->front + 1) % q->size;return p;
}int main(){int M, N;// 读取网格的行数M和列数Nscanf("%d %d", &M, &N);// 动态分配网格数组int **grid = (int**)malloc(sizeof(int*)*M);for(int i = 0; i < M; i++){grid[i] = (int*)malloc(sizeof(int)*N);for(int j = 0; j < N; j++){scanf("%d", &grid[i][j]);}}// 初始化访问标记数组，全部设置为falsebool **visited = (bool**)malloc(sizeof(bool*)*M);for(int i = 0; i < M; i++){visited[i] = (bool*)malloc(sizeof(bool)*N);for(int j = 0; j < N; j++){visited[i][j] = false;}}int max_region = 0; // 记录最大连通区域的大小// 定义四个方向的移动：上、下、左、右int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};// 创建队列，最大可能大小为M*NQueue *q = createQueue(M*N);// 遍历每一个网格点for(int i = 0; i < M; i++){for(int j = 0; j < N; j++){if(!visited[i][j]){// 使用BFS计算当前连通区域的大小enqueue(q, i, j);visited[i][j] = true;int count = 1;while(!isEmpty(q)){Point p = dequeue(q);int x = p.x;int y = p.y;for(int dir = 0; dir < 4; dir++){int new_x = x + dx[dir];int new_y = y + dy[dir];// 判断新位置是否在网格范围内且未被访问if(new_x >=0 && new_x < M && new_y >=0 && new_y < N && !visited[new_x][new_y]){// 判断编号差的绝对值是否小于等于1if(abs(grid[x][y] - grid[new_x][new_y]) <= 1){enqueue(q, new_x, new_y);visited[new_x][new_y] = true;count++;}}}}// 更新最大连通区域的大小if(count > max_region){max_region = count;}}}}// 输出结果printf("%d\n", max_region);// 释放内存for(int i = 0; i < M; i++) {free(grid[i]);free(visited[i]);}free(grid);free(visited);free(q->data);free(q);return 0;
}

九、C++算法源码

// C++版本
#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int M, N;// 读取网格的行数M和列数Ncin >> M >> N;// 初始化网格数组vector<vector<int>> grid(M, vector<int>(N));for(int i = 0; i < M; i++){for(int j = 0; j < N; j++){cin >> grid[i][j];}}// 初始化访问标记数组，全部设置为falsevector<vector<bool>> visited(M, vector<bool>(N, false));int max_region = 0; // 记录最大连通区域的大小// 定义四个方向的移动：上、下、左、右int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};// 遍历每一个网格点for(int i = 0; i < M; i++){for(int j = 0; j < N; j++){if(!visited[i][j]){// 使用BFS计算当前连通区域的大小queue<pair<int, int>> q;q.push({i, j});visited[i][j] = true;int count = 1;while(!q.empty()){pair<int, int> p = q.front();q.pop();int x = p.first;int y = p.second;for(int dir = 0; dir < 4; dir++){int new_x = x + dx[dir];int new_y = y + dy[dir];// 判断新位置是否在网格范围内且未被访问if(new_x >=0 && new_x < M && new_y >=0 && new_y < N && !visited[new_x][new_y]){// 判断编号差的绝对值是否小于等于1if(abs(grid[x][y] - grid[new_x][new_y]) <= 1){q.push({new_x, new_y});visited[new_x][new_y] = true;count++;}}}}// 更新最大连通区域的大小if(count > max_region){max_region = count;}}}}// 输出结果cout << max_region;return 0;
}