时间戳

首页 > 解决方案 > 给定岛的外围标记其在矩阵中的内部（算法）

c++ - 给定岛的外围标记其在矩阵中的内部（算法）

问题描述

我们得到一个大小为 N 的矩阵，它完全用 0 填充，我们还得到一个坐标列表，其中包含一个岛屿外围的坐标。现在我们必须将岛（外围+岛的一部分）标记为1。

我在想出解决这个问题的方法时遇到了麻烦，我想到了 bfs/dfs 但想不出一种方法来实现这个。（请假设只有1个岛并且输入正确，即所有输入坐标形成闭合形状并且有效 

N = 5
coordinates = 
0,2
1,1
1,3
2,0
2,4
3,1
3,3
4,2

所以这就是输出应该是什么样子——

    0 1 2 3 4
  0 0 0 1 0 0
  1 0 1 1 1 0 
  2 1 1 1 1 1 
  3 0 1 1 1 0 
  4 0 0 1 0 0

标记的所有坐标和其中标记的方框都是岛屿的一部分。

标签： c++algorithmc++11matrixgraph-algorithm

解决方案

似乎外围坐标只是填充水平线的末端。

在这种情况下，使用 for 循环将行内的元素设置为 1。伪代码：

lastrow = -1
lastcol = -1  
for every line:
   extract row, col
   if row = lastrow:
       for (i=lastcol + 1; i<=col; i++):   //fill line
          A[row][i] = 1
       lastrow = -1    // to treat possible space in the line
   else:
       A[row][col] = 1     //set the only cell
   lastrow = row
   lastcol = col

推荐阅读