图像物体的边界- 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 200分
题解: Java / Python / C++
题目描述
给定一个二维数组M行N列,二维数组里的数字代表图片的像素,为了简化问题,仅包含像素1和5两种像素,每种像素代表一个物体2个物体相邻的格子为边界,求像素1代表的物体的边界个数。
像素1代表的物体的边界指与像素5相邻的像素1的格子,边界相邻的属于同一个边界,相邻需要考虑8个方向(上,下,左,右,左上,左下,右上,右下)。
其他约束:地图规格约束为:
- 0<M<100
- 0<N<100
输入描述
第一行,行数M, 列数N
第二行开始,是M行N列的像素的二维数组,仅包含像素1和5
输出描述
像素1代表的物体的边界个数。如果没有边界输出0(比如只存在像素1,或者只存在像素5)。
示例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
题解
解题思路
这是一个图的深度优先搜索(DFS)问题。题目要求统计像素1代表的物体的边界个数,而像素1的边界是与像素5相邻的位置。因此,我们可以首先预先处理一下像素5的位置,将与之相邻的像素1标记为可能是边界的位置(用数字0表示)。然后,利用深度优先搜索(DFS)来统计与边界相连的区域的数量,每一轮搜索即为一组边界。
具体步骤如下:
- 读取输入,包括行数
rows
、列数cols
以及像素的二维数组grid
。- 遍历
grid
,当遇到像素值为5时,预先标记其周围8个位置为0,表示可能是边界。这里可以使用两层嵌套循环遍历周围的位置,并将对应位置的像素值标记为0。- 使用深度优先搜索(DFS)来统计与边界相连的区域数量。定义一个函数
dfs
,在该函数中,首先检查当前坐标是否有效且对应位置的像素值为0。如果满足条件,则将当前位置的像素值标记为1,并递归地调用dfs
函数,搜索其周围的8个位置。- 主循环遍历整个二维数组
grid
,对每个像素值为0的位置调用dfs
函数,统计边界的数量。- 输出最终结果。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
// 行数,列数
static int rows, cols;
// 验证坐标有效性
static boolean valid(int r, int c) {
return 0 <= r && r < rows && 0 <= c && c < cols;
}
// 深度优先搜索,标记为 0 的位置就是边界,之后搜索其周围的 0 的位置,并标记为 1 。
// 将所有相关联的都标记为 1
static void dfs(int[][] grid, int r, int c) {
if (!valid(r, c) || grid[r][c] != 0) return;
grid[r][c] = 1;
for (int dr = -1; dr < 2; dr++) {
for (int dc = -1; dc < 2; dc++) {
int nr = r + dr, nc = c + dc;
dfs(grid, nr, nc);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
rows = scanner.nextInt();
cols = scanner.nextInt();
int[][] grid = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
grid[r][c] = scanner.nextInt();
}
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 5) { // 预打标 grid[r][c] = 0, 表示 (r, c) 为边界坐标
for (int dr = -1; dr < 2; dr++) {
for (int dc = -1; dc < 2; dc++) {
int nr = r +
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。