【华为OD机试】图像物体的边界（C++ Java JavaScript Python）

原文链接

【华为OD机试】图像物体的边界（C++ Java JavaScript 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）。

用例

输入	`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
说明	参考题目描述部分

输入	`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
说明	参考题目描述部分

C++

#include <iostream>
#include <vector>
using namespace std;

class UnionFindSet {
public:
  vector<int> fa; // 存储每个节点的父节点，初始化时每个节点的父节点为自己
  int count; // 连通块的个数

  UnionFindSet(int n) { // 初始化并查集，n为节点个数
    fa.resize(n); // 初始化fa数组的大小
    for (int i = 0; i < n; i++) {
      fa[i] = i; // 初始化每个节点的父节点为自己
    }
    count = n; // 初始时有n个连通块
  }

  int Find(int x) { // 查找x所在的连通块的根节点
    if (x != fa[x]) { // 如果x不是根节点
      fa[x] = Find(fa[x]); // 递归查找x的根节点，并将x的父节点设置为根节点，路径压缩优化
    }
    return fa[x]; // 返回x所在的连通块的根节点
  }

  void Union(int x, int y) { // 将x和y所在的连通块合并
    int x_fa = Find(x); // 找到x所在的连通块的根节点
    int y_fa = Find(y); // 找到y所在的连通块的根节点
    if (x_fa != y_fa) { // 如果x和y不在同一个连通块中
      fa[y_fa] = x_fa; // 将y所在的连通块的根节点的父节点设置为x所在的连通块的根节点
      count--; // 连通块的个数减1
    }
  }
};

int getBoundaryCount(vector<vector<int>>& matrix, int m, int n) {
  vector<pair<int, int>> brands; // 存储像素为5的格子的坐标

  // 找到所有像素为5的格子
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (matrix[i][j] == 5) {
        brands.push_back(make_pair(i, j)); // 将像素为5的格子的坐标存入brands中
      }
    }
  }

  int len = brands.size(); // 像素为5的格子的个数
  if (len == 0 || len == n * m) { // 特判：如果没有像素为5的格子或者所有格子都是像素为5的格子，则返回0
    return 0;
  }

  UnionFindSet ufs(len); // 初始化并查集，节点个数为像素为5的格子的个数

  // 对于所有像素为5的格子，如果两个格子之间距离不超过3，则将它们合并到同一个连通块中
  for (int i = 0; i < len; i++) {
    for (int j = i + 1; j < len; j++) {
      int x1 = brands[i].first, y1 = brands[i].second;
      int x2 = brands[j].first, y2 = brands[j].second;

      if (abs(x2 - x1) <= 3 && abs(y2 - y1) <= 3) { // 如果两个格子之间距离不超过3
        ufs.Union(i, j); // 将它们合并到同一个连通块中
      }
    }
  }

  // 统计连通块的个数，即为像素1代表的物体的边界个数
  return ufs.count;
}

int main() {
  vector<vector<int>> matrix;
  int m, n;
  string line;

  // 读入输入数据
  getline(cin, line);
  sscanf(line.c_str(), "%d %d", &m, &n);

  for (int i = 0; i < m; i++) {
    getline(cin, line);
    vector<int> row;
    for (int j = 0; j < n; j++) {
      int num;
      sscanf(line.c_str() + j * 2, "%d", &num); // 读入每个格子的像素值
      row.push_back(num);
    }
    matrix.push_back(row); // 将每一行的像素值存入matrix中
  }

  // 输出结果
  cout << getBoundaryCount(matrix, m, n) << endl;

  return 0;
}

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

原文链接