图像物体的边界
标题：图像物体的边界 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
给定一个二维数组M行N列，二维数组里的数字代表图片的像素，为了简化问题，仅包含像素1和5两种像素，每种像素代表一个物体，2个物体相邻的格子为边界，求像素1代表的物体的边界个数。
像素1代表的物体的边界指与像素5相邻的像素1的格子，边界相邻的属于同一个边界，相邻需要考虑8个方向（上，下，左，右，左上，左下，右上，右下）。
其他约束：
地图规格约束为：
0<M<100
0<N<100
#include<iostream>
#include<vector>
using namespace std;
vector<int> p;
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
void merge(int x, int y) {
p[find(x)] = find(y);
}
bool near5(vector<vector<int>> &grid, int x, int y, int m, int n) {
if (x - 1 >= 0 && grid[x - 1][y] == 5) {
return 1;
}
if (y - 1 >= 0 && x - 1 >= 0 && grid[x - 1][y - 1] == 5) {
return 1;
}
if (y + 1 < n && x - 1 >= 0 && grid[x - 1][y + 1] == 5) {
return 1;
}
if (x + 1 < m && grid[x + 1][y] == 5) {
return 1;
}
if (y - 1 >= 0 && x + 1 < m && grid[x + 1][y - 1] == 5) {
return 1;
}
if (y + 1 < n && x + 1 < m && grid[x + 1][y + 1] == 5) {
return 1;
}
if (y - 1 >= 0 && grid[x][y - 1] == 5) {
return 1;
}
if (y + 1 < n && grid[x][y + 1] == 5) {
return 1;
}
return 0;
}
bool isNear(int a, int b, int n) {
int ax = a / n;
int ay = a % n;
int bx = b /n;
int by = b % n;
return abs(ax - bx) <= 1 && abs(ay - by) <= 1;
}
int main() {
int n;
int m;
cin>>m>>n;
vector<vector<int>> grid(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int a;
cin>>a;
grid[i][j] = a;
}
}
p.resize(m * n);
for (int i = 0; i < m * n; i++) {
p[i] = i;
}
vector<int> list;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && near5(grid, i, j, m, n)) {
list.push_back(i * n + j);
}
}
}
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
if (isNear(list[i], list[j], n)) {
merge(list[i], list[j]);
}
}
}
int ans = 0;
for (int i = 0; i < list.size(); i++) {
if (find(list[i]) == list[i]) {
ans++;
}
}
cout<<ans<<endl;
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
void revert(int **array, int **check, int x, int y, int m, int n) {
if (x >= 0 && x < m && y >= 0 && y < n) {
if (array[x][y] == 1) {
check[x][y] = 1;
}
}
}
void clear_flag(int **check, int x, int y, int m, int n) {
if (!(x >= 0 && x < m && y >= 0 && y < n)) {
return;
}
if (check[x][y] == 0) {
return;
}
check[x][y] = 0;
clear_flag(check, x - 1, y - 1, m, n);
clear_flag(check, x - 1, y, m, n);
clear_flag(check, x - 1, y + 1, m, n);
clear_flag(check, x, y - 1, m, n);
clear_flag(check, x, y + 1, m, n);
clear_flag(check, x + 1, y - 1, m, n);
clear_flag(check, x + 1, y, m, n);
clear_flag(check, x + 1, y + 1, m, n);
}
int scan(int **check, int m, int n) {
int find = FALSE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (check[i][j] == 1) {
find = TRUE;
clear_flag(check, i, j, m, n);
return find;
}
}
}
return find;
}
int main() {
int m, n;
scanf("%d %d", &m, &n);
int **array;
array = (int **)calloc(m, sizeof(int *));
for (int i = 0; i < m; i++) {
array[i] = (int *)calloc(n, sizeof(int));
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &array[i][j]);
}
}
int **check;
check = (int **)calloc(m, sizeof(int *));
for (int i = 0; i < m; i++) {
check[i] = (int *)calloc(n, sizeof(int));
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (array[i][j] == 5) {
revert(array, check, i - 1, j - 1, m, n);
revert(array, check, i - 1, j, m, n);
revert(array, check, i - 1, j + 1, m, n);
revert(array, check, i, j - 1, m, n);
revert(array, check, i, j + 1, m, n);
revert(array, check, i + 1, j - 1, m, n);
revert(array, check, i + 1, j, m, n);
revert(array, check, i + 1, j + 1, m, n);
}
}
}
int count = 0;
int success = TRUE;
while (success) {
success = scan(check, m, n);
count++;
}
count--;
printf("%d", count);
return 0;
}
查看12道真题和解析
联想公司福利 1400人发布