新网站如何做快照今天的新闻
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 。// 将所有相关联的都标记为 1static 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 < colsdef dfs(grid, r, c):# 深度优先搜索，标记为 0 的位置表示边界，然后搜索其周围的 0 的位置，并标记为 1。将所有相关联的位置都标记为 1。if not valid(r, c) or grid[r][c] != 0:returngrid[r][c] = 1for dr in range(-1, 2):for dc in range(-1, 2):nr, nc = r + dr, c + dcdfs(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 + dcif valid(nr, nc) and grid[nr][nc] == 1:grid[nr][nc] = 0 # 标记为可能是边界result = 0for 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;
}
❤️华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏