分割后处理

[编程题]分割后处理

热度指数：1392 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

研究地球空间科学的永强想研究海岸线的长度和海岸线面积之间的关系，为此他找来了很多航拍图像。在航拍图像上利用图像分割的方法，把图像的每个像素标记成陆地（1）和水面（0）。

示例图片：

现在永强想知道每张图中陆地部分的面积。

已知每张图最底部的一条边都是陆地，并且在一张图上陆地都是四邻域联通的。

但是永强发现分割的结果有很多的噪声，于是他定义了如下规则试图去除噪声：

a) 如果一个水面区域被陆地包围，则将这个区域记为陆地；
b) 在a的基础上如果一个陆地区域不和底边的陆地相连，那么这是一个岛屿，不计入陆地的面积。

输入描述:

第一行为两个整数m和n，
接下来m行每行会有n个数，0表示水面，1表示陆地。

输出描述:

去噪后陆地部分的面积。

示例1

输入

5 6
1 0 0 1 0 0
0 0 1 0 1 0
1 1 1 1 1 0
1 0 0 1 1 1
1 1 1 1 1 1

输出

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 850

int grid[MAX_N][MAX_N];

const int dirs[] = {0, -1, 0, 1, 0};

void surround(int m, int n, int x, int y) {
  *(*(grid + y) + x) = 2;
  int i, nx, ny;
  for (i = 0; i < 4; ++i) {
    nx = x + dirs[i], ny = y + dirs[i + 1];
    if (nx < 0 || nx == n || ny < 0 || ny == m || *(*(grid + ny) + nx))
      continue; // 在递归之前拦截 -- 减少递归深度带来的空间负载 overhead
    surround(m, n, nx, ny);
  }
}

int DFS2(int m, int n, int x, int y) {  
  *(*(grid + y) + x) = 0; // mark as seen
  int i, nx, ny, areas = 1;
  for (i = 0; i < 4; ++i) {
    nx = x + dirs[i], ny = y + dirs[i + 1];
    if (nx < 0 || nx == n || ny < 0 || ny == m || *(*(grid + ny) + nx) != 1)
      continue; // 在递归之前拦截 -- 减少递归深度带来的空间负载 overhead
    areas += DFS2(m, n, nx, ny);
  }
  return areas;
}

void print_grid(int m, int n) {
  int x, y;
  for (y = 0; y < m; ++y) {
    for (x = 0; x < n; ++x)
      fprintf(stdout, "%d ", *(*(grid + y) + x));
    fputc(10, stdout);
  }
}

int main(const int argc, const char* const argv[]) {
  int m, n;
  fscanf(stdin, "%d %d", &m, &n);
  
  int x, y;
  for (y = 0; y < m; ++y)
    for (x = 0; x < n; ++x)
      scanf("%d", &grid[y][x]);

  for (x = 0; x < n; ++x) {
    if (grid[0][x] == 0)     surround(m, n, x, 0);
    if (grid[m - 1][x] == 0) surround(m, n, x, m - 1);
  }
  for (y = 0; y < m; ++y) {
    if (grid[y][0] == 0)     surround(m, n, 0, y);
    if (grid[y][n - 1] == 0) surround(m, n, n - 1, y);
  }
  
  int ans = 0;
  for (y = 0; y < m; ++y)
    for (x = 0; x < n; ++x)
      if (!*(*(grid + y) + x)) *(*(grid + y) + x) = 1;
  
  return printf("%d\n", DFS2(m, n, 0, m - 1)), 0; 
}

发表于 2021-08-11 20:16:46 回复(0)