支付宝小程序,搜索引擎禁止的方式优化网站,找个人做网站的,网址导航设主页OD统一考试#xff08;C卷#xff09; 分值#xff1a; 200分 题解#xff1a; Java / Python / C 题目描述
给定一个二维数组M行N列#xff0c;二维数组里的数字代表图片的像素#xff0c;为了简化问题#xff0c;仅包含像素1和5两种像素#xff0c;每种像素代表一个… OD统一考试C卷 分值 200分 题解 Java / Python / C 题目描述
给定一个二维数组M行N列二维数组里的数字代表图片的像素为了简化问题仅包含像素1和5两种像素每种像素代表一个物体2个物体相邻的格子为边界求像素1代表的物体的边界个数。
像素1代表的物体的边界指与像素5相邻的像素1的格子边界相邻的属于同一个边界相邻需要考虑8个方向(上下左右左上左下右上右下)。
其他约束:地图规格约束为:
0M1000N100 输入描述
第一行行数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(vectorvectorint 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;vectorvectorint grid(rows, vectorint(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加群” 整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
