给定一个岛屿的外围，在矩阵中标记其内部（算法）。

Question

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

我很难想出解决这个问题的方法，我想到了bdffss，但想不出实现这个问题的方法。(请假设只有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 

所有标出的坐标和标出的方格都是岛屿的一部分。

Answer 1

如果你知道一个点是在岛内，那么你可以从这个点开始，用基于DFS或BFS的洪水填充来解决这个问题。

不过要可靠地找到这样一个点有点棘手，所以我建议用一个更简单的方法。与其用洪水填充法来找岛内的点 不如从矩阵边界的所有0点开始进行洪水填充来找 不 岛内。 然后设置所有的点，你 没有 发现到1。

Answer 2

看来外围坐标只是填充水平线的末端。

在这种情况下，使用for-loop将线内元素设为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