Для данной периферии острова отметьте его внутреннюю часть в матрице (алгоритм)

Question

Нам дана матрица размера N, которая полностью заполнена нулями, а также нам дан список координат, который содержит координаты периферии острова. Теперь нам нужно пометить остров (периферия + область, которая является частью острова) как единицы.

У меня проблемы с решением этой проблемы, я подумал о 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 

Все координаты отмечены и отмечены квадратные прямоугольники внутри них, которые являются частью острова.

Answer 1

Если вы знаете точку, которая находится внутри острова, вы можете решить эту проблему с помощью заливки на основе DFS или BFS, начиная с этой точки.

Немного сложно найти надежно такую ​​точку , поэтому я предлагаю более простой способ: вместо того, чтобы использовать заливку для поиска точек, которые находятся внутри острова, начните заливку во всех точках 0 вдоль границы матрицы, чтобы найти точки, которые не внутри острова. Затем установите все точки, которые вы не нашли , равными 1.

Answer 2

Кажется, что периферийные координаты - это просто концы закрашенных горизонтальных линий.

В этом случае используйте for-l oop, чтобы установить для элементов внутри строк значение 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