可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练(备注【CSDN】否则不通过)

相关推荐阅读

题目练习网址:【DFS/BFS】2025C-可以组成网络的服务器

题目描述与示例

题目描述

在一个机房中,服务器的位置标识在 n*m 的整数矩阵网格中,1表示单元格上有服务器,0 表示没有。如果两台服务器位于同一行或者同一列中紧邻的位置,则认为它们之间可以组成一个局域网。请你统计机房中最大的局域网包含的服务器个数。

输入描述

第一行输入两个正整数,nm0 < 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或了解更多

更多推荐