Разбираю задачу #200 с литкода, число островов (number of islands).
Задан двумерный массив, в котором участки суши помечены как «1», а участки воды — как «0». Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют единый остров, только если соединяются напрямую по X или по Y (т.е. по диагонали они не соединяются).
Этот вид задач, я отношу к задачам на сегментацию данных, т.к. нам нужно сгруппировать участки суши по заданному признаку.
Изначально не ясно сколько получится островов, а также есть ли в массиве участки суши вообще.
Чтобы понять алгоритм, рассмотрим следующий пример набора данных.
|
1 2 3 4 5 |
grid = [ ["1","1","0","1","0"], ["1","1","0","1","0"], ["0","0","0","0","0"] ] |
Отчетливо видно, что у нас два острова. Но мы это видим, потому что можем анализировать такой небольшой массив как единое целое.
Программа же (если конечно это не нейросеть), должна найти для начала хоть какой то участок суши. Это даст нам определенность, что у нас есть как минимум 1 остров. Мы отметим найденный участок номером острова, и двигаясь к соседним участкам, будем помечать их тем же самым номером острова.
В определенный момент все участки данного острова будет отмечены. Тогда надо опять искать участок суши, который не принадлежит ни одному острову, и повторить выше описанную разметку вновь.
Когда неразмеченные участки суши закончатся, то последний используемый для нумерации островов индекс, позволит нам определить общее число островов.
Если в целом алгоритм ясен, перейдем к деталям, разбирая код (typescript):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
// для сканирования соседних участков я использую стек // со следующей структурой interface IStack { y: number // координаты ячейки x: number netID: number // номер острова, куда присоединить ячейку } function numIslands(grid: string[][]): number { // определим границы сетки const Y = grid.length const X = grid[0].length // чтобы не искать впустую сушу, когда // все ячейки будут размечены, // я подсчитаю общее число ячеек суши заранее // на этапе инициализации let N = 0 // и буду отслеживать число уже размеченных let processed = 0 // пока что мы не знаем сколько островов let lastIsland = 0; // map - это массив размерности grid // где я буду хранить маркировку островов const map: number[][] = [] // специальный стек нужен для сканирования острова const stack: IStack[] = [] // ИНИЦИАЛИЗАЦИЯ // 1. считаем общее число ячеек суши (N) // 2. находим первый участок суши, с которого начнётся // маркировка первого острова for (let y = 0; y < Y; y++) { map[y] = new Array(X).fill(-1) for (let x = 0; x < X; x++) if (grid[y][x] == '1') { if (!stack.length) stack.push({ y, x, netID: ++lastIsland }) N ++ } } // функция маркировки ячеек // 1. устанавливает номер острова для указанной ячейки // 2. ведет подсчет маркированных ячеек const addToMap = (y: number, x: number, islandID: number) => { if (map[y][x] == -1) { map[y][x] = islandID processed ++ } } // СКАНИРОВАНИЕ // x, y - это переменные для поиска следующего участка суши // смотрите далее в коде let x = 0, y = 0; // dt - массив, который формирует правило сегментации: // задаёт смещения к соседним ячейкам по прямой, // как того требует задача. // Если бы можно было присоединять ячейки по диагонали, // то тут было бы 8 элементов const dt = [[0,-1],[0,1],[1,0],[-1,0]] // предварительно высчитанное число ячеек суши N // позволяет задать простой критерий окончания поиска while (processed < N) { // на стеке у нас хранятся варианты сканирования // для текущего острова const state = stack.pop(); if (state) { // маркируем участок addToMap(state.y, state.x, state.netID) // и пытаемся добавить соседние участки на стек dt.forEach(elm => { const dx = elm[0] + state.x const dy = elm[1] + state.y // нам подходят еще пока не размеченные участки суши // заданные правилом сегментации (dt), // но не выходящие за границы карты if (dx >= 0 && dx < X && dy >= 0 && dy < Y) if (map[dy][dx] == -1 && grid[dy][dx] == '1') { stack.push({x: dx, y: dy, netID: state.netID}) } }) } else { // когда стек исчерпал себя, это означает что мы // закончили сканирование очередного острова // и надо найти неразмеченный участок, с которого // мы начнем разметку следующего острова while (true) { if (grid[y][x] == '1' && map[y][x] == -1) { stack.push({y, x, netID: ++lastIsland}) break; } // я не начинаю поиск каждый раз с [0, 0], // a как бы продолжаю поиск с прошлой позиции // это позволяет прилично оптимизировать // поиск для больших массивов со множеством островов x ++; if (x >= X) { x = 0; y ++ if (y >= Y) y = 0 } } } } // номер последнего острова равен общему числу островов return lastIsland; }; |