Определение числа островов в двумерной сетке

Условие

Дана карта, представленная как двумерный массив char[][], где символ '1' обозначает сушу, а '0' — воду. Необходимо вычислить количество островов. Остров представляет собой связную группу ячеек суши, соединённых по горизонтали или вертикали (по диагонали соединения не учитываются).

public static int countIslands(char[][] land) {
    // TODO
}

char[][] islandMap1 = {
    {'1', '1', '0'},
    {'0', '1', '0'},
    {'0', '0', '1'}
};

char[][] islandMap2 = {
    {'1', '0', '0', '0'},
    {'0', '1', '0', '0'},
    {'0', '0', '1', '0'},
    {'0', '0', '0', '1'}
};

Ответ

Каждая ещё не посещённая клетка '1' начинает новый остров. Увеличьте счётчик и обходом по четырём направлениям пометьте всю связанную сушу; диагональные клетки не объединяются.

public static int countIslands(char[][] land) {
    int count = 0;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    var queue = new java.util.ArrayDeque<int[]>();
    for (int r = 0; r < land.length; r++) {
        for (int c = 0; c < land[r].length; c++) {
            if (land[r][c] != '1') continue;
            count++;
            land[r][c] = '0';
            queue.add(new int[]{r,c});
            while (!queue.isEmpty()) {
                int[] p = queue.remove();
                for (int[] d : dirs) {
                    int nr = p[0]+d[0], nc = p[1]+d[1];
                    if (nr >= 0 && nr < land.length && nc >= 0 && nc < land[nr].length
                            && land[nr][nc] == '1') {
                        land[nr][nc] = '0';
                        queue.add(new int[]{nr,nc});
                    }
                }
            }
        }
    }
    return count;
}

Вход меняется на месте, строки массива предполагаются ненулевыми. Для примеров ответы 2 и 4. Время и худшая дополнительная память O(числа клеток).