Count Islands

count_islands.sql

;with m as (
    select *
    from(values
        (0,0,1),(0,1,0),(0,2,1),
        (1,0,1),(1,1,0),(1,2,1),
        (2,0,1),(2,1,1),(2,2,1)
    ) m(r,c,v)
),
label as (
    select r, c, n = 3 * r + c
    from m
    where v = 1),
walk as (
    select r, c, n, path = convert(varchar(8000), n)
    from label
    union all
    select w.r + dr, w.c + dc, w.n, path = concat(path, ':', l.n)
    from walk w
    cross join (values(0, 1), (1, 0), (-1, 0), (0, -1)) deltas(dr, dc)
    join label l
      on l.r = w.r + dr 
     and l.c = w.c + dc
     and l.n not in (
         select value
         from string_split(path, ':'))
)
select count(distinct members)
from (
    select n, members = (
        select distinct value+' '
        from walk w2
        cross apply string_split(path,':') p
        where w2.n = w.n
        for xml path('')
    )
    from walk w
    group by n
) z

CountIslands.cs

// See https://aka.ms/new-console-template for more information
return CountIslands(new[] { new[] { 1, 1, 0 }, new[] { 1, 0, 1 }, new[] { 0, 1, 1 } }));


static int CountIslands(int[][] m)
{
    int count = 0;
    for (int i = 0; i < m.Length; i++)
    for (int j = 0; j < m[i].Length; j++)
    if (m[i][j] == 1)
    {
        count+= Walk(m, i, j);
    }
    return count;
}

static int Walk(int[][] m, int i, int j)
{
    if ((uint)i < (uint)m.Length &&
        (uint)j < (uint)m[i].Length &&
        m[i][j] == 1)
    {
        m[i][j] = 0;
        Walk(m, i, j + 1);
        Walk(m, i, j - 1);
        Walk(m, i + 1, j);
        Walk(m, i - 1, j);
    }
    return 1;
}