最新华为OD机试真题-图像物体的边界(200分)

🍭 大家好这里是清隆Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎 在线评测链接

图像物体的边界(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🪐 图像物体的边界

题目描述

给定一个二维数组 行 列，二维数组里的数字代表图片的像素。为了简化问题，像素仅包含 和 两种像素，每种像素代表一个物体。 个物体相邻的格子为边界，求像素 代表的物体的边界数目，即与像素 相邻的像素 的格子数目，且相邻的属于同一个边界。相邻需要考虑 个方向（上、下、左、右、左上、左下、右上、右下）。

输入描述

第一行包含两个正整数 和 ，表示二维数组的行数和列数。

接下来的 行，每行包含 个数字，表示二维数组的像素。

输出描述

输出像素 代表的物体的边界数目。如果没有边界，输出 （例如只存在像素 ，或者只存在像素 ）。

样例1

输入

6 6
1 1 1 1 1 1
1 5 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 5

输出

2

样例2

输入

6 6
1 1 1 1 1 1
1 5 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 5 1
1 1 1 1 1 1

输出

1

数据范围

参考代码

• Python

import sys

# 定义8个方向的偏移量
dx = [0, 0, -1, 1, -1, 1, -1, 1]
dy = [-1, 1, 0, 0, -1, 1, 1, -1]

# 增加递归深度限制
sys.setrecursionlimit(10 ** 6)

# DFS函数，用于遍历相连的边界
def dfs(x, y, border, visited, m, n):
    if x < 1 or x > m or y < 1 or y > n or border[x][y] == 0 or visited[x][y] == 1:
        return
    visited[x][y] = 1
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        dfs(nx, ny, border, visited, m, n)

def main():
    # 读取输入
    m, n = map(int, input().split())
    grid = [[1]]  # 添加一个哨兵行
    for _ in range(m):
        grid.append([0] + list(map(int, input().split())))  # 添加哨兵列
    
    # 初始化边界数组和访问数组
    border = [[0] * (n + 1) for _ in range(m + 1)]
    visited = [[0] * (n + 1) for _ in range(m + 1)]

    # 标记边界
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if grid[i][j] == 5:
                for k in range(8):
                    ni, nj = i + dx[k], j + dy[k]
                    if 1 <= ni <= m and 1 <= nj <= n and grid[ni][nj] == 1:
                        border[ni][nj] = 1

    # 计算边界数量
    count = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if border[i][j] == 1 and not visited[i][j]:
                count += 1
                dfs(i, j, border, visited, m, n)

    print(count)

if __name__ == "__main__":
    main()

• Java

import java.util.*;

public class Main {
    // 定义8个方向的偏移量
    static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1};
    static int[] dy = {-1, 1, 0, 0, -1, 1, 1, -1};
    
    // DFS函数，用于遍历相连的边界
    static void dfs(int x, int y, int[][] border, boolean[][] visited, int m,