Number of Islands

Um mapa chega como uma lista de linhas de mesmo comprimento. Cada caractere é 1, um quadrado de terra, ou 0, um quadrado de água. Dois quadrados de terra pertencem à mesma ilha quando um está diretamente acima, abaixo, à esquerda ou à direita do outro. Quadrados que apenas se tocam em um canto não estão conectados.

Considere o mapa ["11000", "11000", "00100", "00011"]:

• os quatro quadrados de terra no canto superior esquerdo formam uma ilha,
• o único quadrado na linha do meio é uma segunda ilha, pois só toca a primeira em um canto,
• os dois quadrados no canto inferior direito formam uma terceira.

Então, o mapa contém 3 ilhas.

O mapa é, na verdade, um grafo: cada quadrado de terra é um nó, e uma aresta conecta dois quadrados de terra que compartilham um lado. Contar ilhas significa contar as partes conectadas desse grafo. Sempre que você encontra um quadrado de terra que ainda não visitou, encontrou uma nova ilha e explora toda ela antes de continuar.

Escreva uma função chamada numIslands que recebe grid, uma lista de strings compostas por 1 (terra) e 0 (água), e retorna o número de ilhas. Uma ilha é um grupo de quadrados de terra conectados para cima, para baixo, à esquerda ou à direita.

Por exemplo, ["01110", "01000", "00011", "11001"] retorna 3: a forma nas linhas superiores, o grupo à direita e o par no canto inferior esquerdo.

Restrições: 1 <= número de linhas, número de colunas <= 150. Todas as linhas têm o mesmo comprimento.