最新华为OD机试真题-图像物体的边界(200分)
🍭 大家好这里是清隆Coding ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎 在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓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,
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
最新华为OD机试-E+D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测