(200分)- 图像物体的边界（Java JS Python）

(200分)- 图像物体的边界（Java & JS & Python）

题目描述

给定一个二维数组M行N列，二维数组里的数字代表图片的像素，为了简化问题，仅包含像素1和5两种像素，每种像素代表一个物体，2个物体相邻的格子为边界，求像素1代表的物体的边界个数。

像素1代表的物体的边界指与像素5相邻的像素1的格子，边界相邻的属于同一个边界，相邻需要考虑8个方向（上，下，左，右，左上，左下，右上，右下）。

其他约束

地图规格约束为：

0<M<100
0<N<100

1）如下图，与像素5的格子相邻的像素1的格子（0,0）、（0,1）、（0,2）、（1,0）、（1,2）、（2,0）、（2,1）、（2,2）、（4,4）、（4,5）、（5,4）为边界，另（0,0）、（0,1）、（0,2）、（1,0）、（1,2）、（2,0）、（2,1）、（2,2）相邻，为1个边界，（4,4）、（4,5）、（5,4）相邻，为1个边界，所以下图边界个数为2。

2）如下图，与像素5的格子相邻的像素1的格子（0,0）、（0,1）、（0,2）、（1,0）、（1,2）、（2,0）、（2,1）、（2,2）、（3,3）、（3,4）、（3,5）、（4,3）、（4,5）、（5,3）、（5,4）、（5,5）为边界，另这些边界相邻，所以下图边界个数为1。

注：（2,2）、（3,3）相邻。

输入描述

第一行，行数M，列数N

第二行开始，是M行N列的像素的二维数组，仅包含像素1和5

输出描述

像素1代表的物体的边界个数。

如果没有边界输出0（比如只存在像素1，或者只存在像素5）。

用例

题目解析

本题可以使用并查集。

有几个像素5，我们就可以先假设有几个不相邻的边界。

判断两个边界相邻的条件是：两个像素5的坐标满足以下关系：|x1-x2| ≤ 3 且 |y1-y2| ≤ 3。

如图所示，绿色线表示另一个像素5的移动范围边界。

因此，本题可以转化为使用并查集算法来判断像素5是否连通。

。

上面思路其实存在一定偏差。

因为本题要求解的是：像素1代表的物体的边界个数。我们可以看一个例子：

上

根据图示，应该存在几个边界？

如果按照之前的思路，只存在1个边界。但这种理解存在问题，因为题目明确要求：

像素1代表的物体边界是指与像素5相邻的像素1的格子，且相邻的边界属于同一边界。

在图中，两个像素1格子并不相邻，因此不能视为同一边界。

我的解题步骤如下：

1. 遍历矩阵，提取所有与像素5相邻的像素1（边界）坐标
2. 使用并查集算法对这些边界像素1进行合并：
   • 合并条件：两个格子的横向和纵向距离均不超过1（即相邻）
   • 符合此条件的边界像素将被合并为同一边界

Java算法源码

import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] matrix = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = sc.nextInt(); } } System.out.println(getResult(matrix, m, n)); } public static int getResult(int[][] matrix, int m, int n) { // 上、下、左、右、左上、左下、右上、右下的横坐标、纵坐标偏移量 int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; // 记录所有边界位置 HashSet<Integer> brands = new HashSet<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 如果当前点是像素5 if (matrix[i][j] == 5) { // 遍历像素5的相邻位置 for (int[] offset : offsets) { int newI = i + offset[0]; int newJ = j + offset[1]; // 如果该位置不越界，且为像素1，则是边界 if (newI >= 0 && newI < m && newJ >= 0 && newJ < n && matrix[newI][newJ] == 1) { brands.add(newI * n + newJ); } } } } } ArrayList<Integer> brands_list = new ArrayList<>(brands); int k = brands_list.size(); // 使用并查集，对所有边界位置进行合并 UnionFindSet ufs = new UnionFindSet(k); for (int i = 0; i < k; i++) { int x1 = brands_list.get(i) / n; int y1 = brands_list.get(i) % n; for (int j = i + 1; j < k; j++) { int x2 = brands_list.get(j) / n; int y2 = brands_list.get(j) % n; // 如果两个边界像素1的位置 横向、纵向距离均小于1，则相邻，可以进行合并 if (Math.abs(x1 - x2) <= 1 && Math.abs(y1 - y2) <= 1) { ufs.union(i, j); } } } return ufs.count; } } class UnionFindSet { int[] fa; int count; public UnionFindSet(int n) { this.count = n; this.fa = new int[n]; for (int i = 0; i < n; i++) this.fa[i] = i; } public int find(int x) { if (x != this.fa[x]) { return (this.fa[x] = this.find(this.fa[x])); } return x; } public void union(int x, int y) { int x_fa = this.find(x); int y_fa = this.find(y); if (x_fa != y_fa) { this.fa[y_fa] = x_fa; this.count--; } } }

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { const [m, n] = (await readline()).split(" ").map(Number); const matrix = []; for (let i = 0; i < m; i++) { matrix.push((await readline()).split(" ").map(Number)); } console.log(getBrandCount(matrix, m, n)); })(); function getBrandCount(matrix, m, n) { // 上、下、左、右、左上、左下、右上、右下的横坐标、纵坐标偏移量 const offsets = [ [-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1], ]; // 记录所有边界位置 const brands = new Set(); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { // 如果当前点是像素5 if (matrix[i][j] === 5) { // 遍历像素5的相邻位置 for (let offset of offsets) { const newI = i + offset[0]; const newJ = j + offset[1]; // 如果该位置不越界，且为像素1，则是边界 if ( newI >= 0 && newI < m && newJ >= 0 && newJ < n && matrix[newI][newJ] == 1 ) { brands.add(newI * n + newJ); } } } } } const brands_list = [...brands]; const k = brands_list.length; // 使用并查集，对所有边界位置进行合并 const ufs = new UnionFindSet(k); for (let i = 0; i < k; i++) { const x1 = Math.floor(brands_list[i] / n); const y1 = brands_list[i] % n; for (let j = i + 1; j < k; j++) { const x2 = Math.floor(brands_list[j] / n); const y2 = brands_list[j] % n; // 如果两个边界像素1的位置 横向、纵向距离均小于1，则相邻，可以进行合并 if (Math.abs(x1 - x2) <= 1 && Math.abs(y1 - y2) <= 1) { ufs.union(i, j); } } } return ufs.count; } class UnionFindSet { constructor(n) { this.fa = []; for (let i = 0; i < n; i++) { this.fa.push(i); } this.count = n; } find(x) { if (x !== this.fa[x]) { this.fa[x] = this.find(this.fa[x]); return this.fa[x]; } return x; } union(x, y) { let x_fa = this.find(x); let y_fa = this.find(y); if (x_fa !== y_fa) { this.fa[y_fa] = x_fa; this.count--; } } }

Python算法源码

# 输入获取 m, n = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(m)] # 并查集 class UnionFindSet: def __init__(self, n): self.fa = [idx for idx in range(n)] self.count = n def find(self, x): if x != self.fa[x]: self.fa[x] = self.find(self.fa[x]) return self.fa[x] return x def union(self, x, y): x_fa = self.find(x) y_fa = self.find(y) if x_fa != y_fa: self.fa[y_fa] = x_fa self.count -= 1 # 算法入口 def getResult(): # 上、下、左、右、左上、左下、右上、右下的横坐标、纵坐标偏移量 offsets = ((-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)) # 记录所有边界位置 brands = set() for i in range(m): for j in range(n): # 如果当前点是像素5 if matrix[i][j] == 5: # 遍历像素5的相邻位置 for offset in offsets: newI = i + offset[0] newJ = j + offset[1] # 如果该位置不越界，且为像素1，则是边界 if m > newI >= 0 and n > newJ >= 0 and matrix[newI][newJ] == 1: brands.add(newI * n + newJ) brands_list = list(brands) k = len(brands_list) # 使用并查集，对所有边界位置进行合并 ufs = UnionFindSet(k) for i in range(k): x1 = brands_list[i] // n y1 = brands_list[i] % n for j in range(i + 1, k): x2 = brands_list[j] // n y2 = brands_list[j] % n # 如果两个边界像素1的位置 横向、纵向距离均小于1，则相邻，可以进行合并 if abs(x1 - x2) <= 1 and abs(y1 - y2) <= 1: ufs.union(i, j) return ufs.count # 算法调用 print(getResult())