20天拿下华为OD笔试之【DFS/BFS】2025C-可以组成网络的服务器【Py/Java/C++/C/JS/Go六种语言OD独家2025C卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解
·
可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳od1441了解算法冲刺训练(备注【CSDN】否则不通过)
文章目录
相关推荐阅读
- 【华为OD机考】2025C+2025B+2024E+D卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】
- 【华为OD笔试】2025C+2025B+2024E+D卷真题机考套题汇总【真实反馈,不断更新,限时免费】
- 【华为OD笔试】2024E+D卷命题规律解读【分析500+场OD笔试考点总结】
- 【华为OD流程】性格测试选项+注意事项】
题目练习网址:【DFS/BFS】2025C-可以组成网络的服务器
题目描述与示例
题目描述
在一个机房中,服务器的位置标识在 n*m 的整数矩阵网格中,1表示单元格上有服务器,0 表示没有。如果两台服务器位于同一行或者同一列中紧邻的位置,则认为它们之间可以组成一个局域网。请你统计机房中最大的局域网包含的服务器个数。
输入描述
第一行输入两个正整数,n和m,0 < n,m <= 100
之后为n*m的二维数组,代表服务器信息
输出描述
最大局域网包含的服务器个数。
示例
输入
2 2
1 0
1 1
输出
3
补充说明
[0][0]、[1][0]、[1][1]三台服务器相互连接,可以组成局域网
解题思路
注意,本题和LeetCode695、岛屿的最大面积 完全一致,直接套模板即可。
代码
解法一:DFS
Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例!
# 地址:https://www.odalgo.com
# 华为OD机试刷题网站:https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频
# 题目:2023A/2024E/2025C-可以组成网络的服务器
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:DFS
# 代码看不懂的地方,请直接在群上提问
import sys
sys.setrecursionlimit(10000)
# 初始化上下左右四个方向的数组
DERICTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
# 构建DFS函数
def DFS(grid, i, j, checkList):
global area
# 将该点标记为已经检查过
checkList[i][j] = True
# 面积增大
area += 1
# 遍历上下左右四个方向的邻点坐标
for dx, dy in DERICTIONS:
next_i, next_j = i + dx, j + dy
# 若近邻点满足三个条件:
# 1.没有越界 2. 近邻点尚未被检查过 3.近邻点也为陆地
if ((0 <= next_i < n and 0 <= next_j < m) and checkList[next_i][next_j] == False
and grid[next_i][next_j] == 1):
# 对近邻点(ni, nj)进行DFS搜索
DFS(grid, next_i, next_j, checkList)
# 输入长、宽
n, m = map(int, input().split())
# 构建网格
grid = list()
for _ in range(n):
grid.append(list(map(int, input().split())))
ans = 0
# 初始化数组checkList用于DFS遍历过程中的检查
# 0表示尚未访问,1表示已经访问
checkList = [[False] * m for _ in range(n)]
# 对整个grid二维数组进行双重循环遍历
for i in range(n):
for j in range(m):
# 若该点为陆地且还没有进行过搜寻
if grid[i][j] == 1 and checkList[i][j] == False:
# 在每一次DFS之前,先初始化面积为0
area = 0
# 可以进行DFS
DFS(grid, i, j, checkList)
# 做完DFS,更新ans
ans = max(ans, area)
print(ans)
Java
import java.util.Scanner;
public class Main {
static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static int n, m;
static int[][] grid;
static boolean[][] checkList;
static int area;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
grid = new int[n][m];
checkList = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !checkList[i][j]) {
area = 0;
DFS(i, j);
ans = Math.max(ans, area);
}
}
}
System.out.println(ans);
}
static void DFS(int i, int j) {
checkList[i][j] = true;
area++;
for (int[] dir : DIRECTIONS) {
int nextI = i + dir[0];
int nextJ = j + dir[1];
if (isValid(nextI, nextJ) && !checkList[nextI][nextJ] && grid[nextI][nextJ] == 1) {
DFS(nextI, nextJ);
}
}
}
static boolean isValid(int i, int j) {
return i >= 0 && i < n && j >= 0 && j < m;
}
}
C++
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n, m;
vector<vector<int>> grid;
vector<vector<bool>> checkList;
int area;
void DFS(int i, int j) {
checkList[i][j] = true;
area++;
for (auto dir : DIRECTIONS) {
int nextI = i + dir.first;
int nextJ = j + dir.second;
if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < m && !checkList[nextI][nextJ] && grid[nextI][nextJ] == 1) {
DFS(nextI, nextJ);
}
}
}
int main() {
cin >> n >> m;
grid.resize(n, vector<int>(m));
checkList.resize(n, vector<bool>(m, false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && !checkList[i][j]) {
area = 0;
DFS(i, j);
ans = max(ans, area);
}
}
}
cout << ans << endl;
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
/* 方向数组:右、下、左、上 */
static const int dx[4] = {0, 1, 0, -1};
static const int dy[4] = {1, 0, -1, 0};
int n, m;
int **grid; /* 网格:0/1 */
char **checkList; /* 访问标记:0/1 */
int area; /* 当前连通块面积 */
/* 深度优先搜索:从 (i,j) 出发,统计当前连通块面积 */
void DFS(int i, int j) {
checkList[i][j] = 1; /* 标记已访问 */
area++;
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni >= 0 && ni < n && nj >= 0 && nj < m &&
!checkList[ni][nj] && grid[ni][nj] == 1) {
DFS(ni, nj);
}
}
}
int main(void) {
if (scanf("%d %d", &n, &m) != 2) return 0;
/* 分配网格与访问标记内存 */
grid = (int **)malloc(sizeof(int *) * n);
checkList = (char **)malloc(sizeof(char *) * n);
if (!grid || !checkList) return 1;
for (int i = 0; i < n; ++i) {
grid[i] = (int *)malloc(sizeof(int) * m);
checkList[i] = (char *)calloc(m, sizeof(char)); /* 初始化为 0(未访问) */
if (!grid[i] || !checkList[i]) return 1;
}
/* 读取网格 */
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &grid[i][j]);
}
}
int ans = 0;
/* 遍历所有格子,遇到未访问的 1 则启动一轮 DFS 并更新最大面积 */
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1 && !checkList[i][j]) {
area = 0;
DFS(i, j);
if (area > ans) ans = area;
}
}
}
/* 输出最大连通块面积 */
printf("%d\n", ans);
/* 释放内存 */
for (int i = 0; i < n; ++i) {
free(grid[i]);
free(checkList[i]);
}
free(grid);
free(checkList);
return 0;
}
Node JavaScript
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let p = 0;
// 读取 n, m
const n = data[p++], m = data[p++];
// 读取网格
const grid = Array.from({ length: n }, () => Array(m));
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) grid[i][j] = data[p++];
}
// 访问标记
const vis = Array.from({ length: n }, () => Array(m).fill(false));
// 方向:右、下、左、上
const DIR = [[0,1],[1,0],[0,-1],[-1,0]];
function inBounds(i, j) {
return i >= 0 && i < n && j >= 0 && j < m;
}
let ans = 0;
// 遍历所有格子,遇到未访问的 1,做一轮 DFS 统计联通块面积
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] === 1 && !vis[i][j]) {
let area = 0;
const st = [[i, j]];
vis[i][j] = true;
while (st.length) {
const [x, y] = st.pop();
area++;
for (const [dx, dy] of DIR) {
const nx = x + dx, ny = y + dy;
if (inBounds(nx, ny) && !vis[nx][ny] && grid[nx][ny] === 1) {
vis[nx][ny] = true;
st.push([nx, ny]);
}
}
}
if (area > ans) ans = area;
}
}
}
console.log(ans.toString());
Go
package main
import (
"bufio"
"fmt"
"os"
)
var (
n, m int
grid [][]int
vis [][]bool
DIR = [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
)
func inBounds(i, j int) bool {
return i >= 0 && i < n && j >= 0 && j < m
}
// DFS 返回从 (i,j) 出发的连通块面积(仅访问值为 1 的格子)
func dfs(i, j int) int {
vis[i][j] = true
area := 1
for _, d := range DIR {
ni, nj := i+d[0], j+d[1]
if inBounds(ni, nj) && !vis[ni][nj] && grid[ni][nj] == 1 {
area += dfs(ni, nj)
}
}
return area
}
func main() {
in := bufio.NewReader(os.Stdin)
fmt.Fscan(in, &n, &m)
grid = make([][]int, n)
for i := 0; i < n; i++ {
grid[i] = make([]int, m)
for j := 0; j < m; j++ {
fmt.Fscan(in, &grid[i][j])
}
}
vis = make([][]bool, n)
for i := 0; i < n; i++ {
vis[i] = make([]bool, m)
}
ans := 0
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 1 && !vis[i][j] {
area := dfs(i, j)
if area > ans {
ans = area
}
}
}
}
fmt.Println(ans)
}
解法二:BFS
Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例!
# 地址:https://www.odalgo.com
# 华为OD机试刷题网站:https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频
# 题目:2023A/2024E/2025C-可以组成网络的服务器
# 分值:200
# 作者:闭着眼睛学数理化
# 算法:BFS
# 代码看不懂的地方,请直接在群上提问
from collections import deque
# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
# 输入长、宽
n, m = map(int, input().split())
# 构建网格
grid = list()
for _ in range(n):
grid.append(list(map(int, input().split())))
ans = 0
# 初始化和grid一样大小的二维数组checkList用于DFS遍历过程中的检查
checkList = [[0] * m for _ in range(n)]
# 双重遍历grid数组
for i in range(n):
for j in range(m):
# 若该点为1且还没有进行过搜寻
# 找到了一个BFS搜索的起始位置(i,j)
if grid[i][j] == 1 and checkList[i][j] == 0:
# 对于该片连通块,构建一个队列,初始化包含该点
q = deque()
q.append((i, j))
# 修改checkList[i][j]为1,表示该点已经搜寻过
checkList[i][j] = 1
# 进行BFS之前,初始化该连通块的面积为0
area = 0
# 进行BFS,退出循环的条件是队列为空
while len(q) > 0:
# 弹出栈队头的点(x,y) 搜寻该点上下左右的近邻点
x, y = q.popleft()
area += 1
# 遍历(x,y)上下左右的四个方向的近邻点
for dx, dy in DIRECTIONS:
x_next, y_next = x+dx, y+dy
# 如果近邻点满足三个条件
if (0 <= x_next < n and 0 <= y_next < m and checkList[x_next][y_next] == 0
and grid[x_next][y_next] == 1):
# 对近邻点做两件事:
# 1. 入队 2. 标记为已检查过
q.append((x_next, y_next))
checkList[x_next][y_next] = 1
# 更新答案
ans = max(ans, area)
print(ans)
Java
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
int ans = 0;
int[][] checkList = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1 && checkList[i][j] == 0) {
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{i, j});
checkList[i][j] = 1;
int area = 0;
while (!queue.isEmpty()) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
area++;
for (int[] dir : DIRECTIONS) {
int xNext = x + dir[0];
int yNext = y + dir[1];
if (xNext >= 0 && xNext < n && yNext >= 0 && yNext < m
&& checkList[xNext][yNext] == 0 && grid[xNext][yNext] == 1) {
queue.offer(new int[]{xNext, yNext});
checkList[xNext][yNext] = 1;
}
}
}
ans = Math.max(ans, area);
}
}
}
System.out.println(ans);
}
}
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
vector<vector<int>> checkList(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1 && checkList[i][j] == 0) {
queue<pair<int, int>> q;
q.push({i, j});
checkList[i][j] = 1;
int area = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
area++;
for (auto dir : DIRECTIONS) {
int x_next = x + dir.first;
int y_next = y + dir.second;
if (x_next >= 0 && x_next < n && y_next >= 0 && y_next < m &&
checkList[x_next][y_next] == 0 && grid[x_next][y_next] == 1) {
q.push({x_next, y_next});
checkList[x_next][y_next] = 1;
}
}
}
ans = max(ans, area);
}
}
}
cout << ans << endl;
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
/* 四个方向:右、下、左、上 */
static const int dx[4] = {0, 1, 0, -1};
static const int dy[4] = {1, 0, -1, 0};
/* 简单点对结构,表示网格中的一个格子坐标 */
typedef struct {
int x, y;
} Pair;
int main(void) {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
/* 分配网格与访问标记 */
int **grid = (int **)malloc(n * sizeof(int *));
char **vis = (char **)malloc(n * sizeof(char *)); /* 0/1 标记是否访问 */
if (!grid || !vis) return 1;
for (int i = 0; i < n; ++i) {
grid[i] = (int *)malloc(m * sizeof(int));
vis[i] = (char *)calloc(m, sizeof(char));
if (!grid[i] || !vis[i]) return 1;
for (int j = 0; j < m; ++j) {
scanf("%d", &grid[i][j]);
}
}
/* 队列:最多 n*m 个元素(每个格子最多入队一次) */
Pair *queue = (Pair *)malloc((size_t)n * m * sizeof(Pair));
if (!queue) return 1;
int ans = 0;
/* 遍历所有格子,遇到“未访问的 1”就启动一轮 BFS */
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 1 && vis[i][j] == 0) {
int head = 0, tail = 0; /* 队头、队尾指针 */
int area = 0; /* 当前连通块面积 */
/* 起点入队并标记访问 */
queue[tail++] = (Pair){i, j};
vis[i][j] = 1;
/* BFS:不断弹出队头,检查四邻接 */
while (head < tail) {
Pair cur = queue[head++];
int x = cur.x, y = cur.y;
area++;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
vis[nx][ny] == 0 && grid[nx][ny] == 1) {
vis[nx][ny] = 1;
queue[tail++] = (Pair){nx, ny};
}
}
}
if (area > ans) ans = area;
}
}
}
/* 输出最大连通块面积 */
printf("%d\n", ans);
/* 释放内存 */
free(queue);
for (int i = 0; i < n; ++i) {
free(grid[i]);
free(vis[i]);
}
free(grid);
free(vis);
return 0;
}
Node JavaScript
const fs = require("fs");
const input = fs.readFileSync(0, "utf8").trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++], m = input[idx++];
// 读取网格
const grid = Array.from({ length: n }, () => Array(m));
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
grid[i][j] = input[idx++];
}
}
// 访问标记
const checkList = Array.from({ length: n }, () => Array(m).fill(0));
// 四个方向:右、下、左、上
const DIRECTIONS = [[0, 1], [1, 0], [0, -1], [-1, 0]];
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] === 1 && checkList[i][j] === 0) {
let queue = [[i, j]];
checkList[i][j] = 1;
let area = 0;
while (queue.length > 0) {
const [x, y] = queue.shift();
area++;
for (const [dx, dy] of DIRECTIONS) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
checkList[nx][ny] === 0 && grid[nx][ny] === 1) {
queue.push([nx, ny]);
checkList[nx][ny] = 1;
}
}
}
ans = Math.max(ans, area);
}
}
}
console.log(ans.toString());
Go
package main
import (
"bufio"
"fmt"
"os"
)
var (
n, m int
grid [][]int
vis [][]bool
DIR = [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
)
func inBounds(i, j int) bool {
return i >= 0 && i < n && j >= 0 && j < m
}
func bfs(si, sj int) int {
queue := [][2]int{{si, sj}}
vis[si][sj] = true
area := 0
for len(queue) > 0 {
p := queue[0]
queue = queue[1:]
x, y := p[0], p[1]
area++
for _, d := range DIR {
nx, ny := x+d[0], y+d[1]
if inBounds(nx, ny) && !vis[nx][ny] && grid[nx][ny] == 1 {
vis[nx][ny] = true
queue = append(queue, [2]int{nx, ny})
}
}
}
return area
}
func main() {
in := bufio.NewReader(os.Stdin)
fmt.Fscan(in, &n, &m)
grid = make([][]int, n)
for i := 0; i < n; i++ {
grid[i] = make([]int, m)
for j := 0; j < m; j++ {
fmt.Fscan(in, &grid[i][j])
}
}
vis = make([][]bool, n)
for i := 0; i < n; i++ {
vis[i] = make([]bool, m)
}
ans := 0
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 1 && !vis[i][j] {
area := bfs(i, j)
if area > ans {
ans = area
}
}
}
}
fmt.Println(ans)
}
时空复杂度
时间复杂度:O(NM)。
空间复杂度:O(NM)。
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务1000+同学成功上岸!
-
课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
90+天陪伴式学习,100+直播课时,300+动画图解视频,500+LeetCode经典题,500+华为OD真题/大厂真题,还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接OD真题汇总(持续更新)
-
绿色聊天软件戳
od1441或了解更多
更多推荐



所有评论(0)