(200分)- 图像物体的边界Java JS Python题目描述给定一个二维数组M行N列二维数组里的数字代表图片的像素为了简化问题仅包含像素1和5两种像素每种像素代表一个物体2个物体相邻的格子为边界求像素1代表的物体的边界个数。像素1代表的物体的边界指与像素5相邻的像素1的格子边界相邻的属于同一个边界相邻需要考虑8个方向上下左右左上左下右上右下。其他约束地图规格约束为0M1000N1001如下图与像素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。用例输入6 61 1 1 1 1 11 5 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 5输出2说明参考题目描述部分输入6 61 1 1 1 1 11 5 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 5 11 1 1 1 1 1输出1说明参考题目描述部分题目解析本题可以使用并查集。有几个像素5我们就可以先假设有几个不相邻的边界。判断两个边界相邻的条件是两个像素5的坐标满足以下关系|x1-x2| ≤ 3 且 |y1-y2| ≤ 3。如图所示绿色线表示另一个像素5的移动范围边界。因此本题可以转化为使用并查集算法来判断像素5是否连通。。上面思路其实存在一定偏差。因为本题要求解的是像素1代表的物体的边界个数。我们可以看一个例子上根据图示应该存在几个边界如果按照之前的思路只存在1个边界。但这种理解存在问题因为题目明确要求像素1代表的物体边界是指与像素5相邻的像素1的格子且相邻的边界属于同一边界。在图中两个像素1格子并不相邻因此不能视为同一边界。我的解题步骤如下遍历矩阵提取所有与像素5相邻的像素1边界坐标使用并查集算法对这些边界像素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}}; // 记录所有边界位置 HashSetInteger 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); } } } } } ArrayListInteger 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())