图像物体的边界- 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

给定一个二维数组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 + dr, nc = c + dc;
                            if (valid(nr, nc) && grid[nr][nc] == 1) {
                                grid[nr][nc] = 0;   // 标记为可能是边界
                            }
                        }
                    }
                }

            }
        }

        int result = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 0) {
                    // 每一轮搜索即为一组边界
                    dfs(grid, r, c);
                    result++;
                }
            }
        }

        System.out.println(result);
    }
}

Python

def valid(r, c):
    # 验证坐标的有效性
    return 0 <= r < rows and 0 <= c < cols


def dfs(grid, r, c):
    # 深度优先搜索，标记为 0 的位置表示边界，然后搜索其周围的 0 的位置，并标记为 1。将所有相关联的位置都标记为 1。
    if not valid(r, c) or grid[r][c] != 0:
        return
    grid[r][c] = 1

    for dr in range(-1, 2):
        for dc in range(-1, 2):
            nr, nc = r + dr, c + dc
            dfs(grid, nr, nc)


if __name__ == "__main__":
    # 读取输入
    rows, cols = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(rows)]

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 5:
                # 预先标记 grid[r][c] = 0，表示 (r, c) 为边界坐标
                for dr in range(-1, 2):
                    for dc in range(-1, 2):
                        nr, nc = r + dr, c + dc
                        if valid(nr, nc) and grid[nr][nc] == 1:
                            grid[nr][nc] = 0  # 标记为可能是边界

    result = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:
                # 使用深度优先搜索统计与边界相连的区域数量
                dfs(grid, r, c)
                result += 1

    # 输出结果
    print(result)

C++

#include <bits/stdc++.h>
using namespace std;

int rows, cols;

// 验证坐标有效性
bool valid(int r, int c)
{
    return 0 <= r && r < rows && 0 <= c && c < cols;
}

// 深度优先搜索，标记为 0 的位置就是边界，之后搜索其周围的 0 的位置，并标记为 1 。
// 将所有相关联的都标记为 1
void dfs(vector<vector<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);
        }
    }
}

int main()
{
    cin >> rows >> cols;
    vector<vector<int>> grid(rows, vector<int>(cols, 0));

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            cin >> grid[r][c];
        }
    }

    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 + dr, nc = c + dc;
                        if (valid(nr, nc) && grid[nr][nc] == 1) {
                            grid[nr][nc] = 0;   // 标记为可能是边界
                        }
                    }
                }
            }
        }
    }

    int result = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 0) {
                dfs(grid, r, c);
                result++;
            }
        }
    }

    cout << result << endl;
}