200. Number of Islands #97
Description
https://leetcode.com/problems/number-of-islands/
Soru: Burada bize m x n 2D bir char arrayi veriliyor. Bu array üzerinde karaları '1', suları '0' karakterleri simgeliyor.
Buradaki "ada"ların sayısını döndürmemiz isteniyor.
"Ada" denilen şeyi, birbirine 4 düz taraftan, yatay ya da dikey, bağlı 1 değerleri oluşturuyor:
0 0 1
1 1 0
1 0 0
Örneğin burada 2 ada var, biri 3 büyüklüğünde olan, öbürü sağ üst, çaprazda olduğu için bağımsız. Leetcode'da 2 daha büyük örnek verilmiş.
Grid'in dışındaki array-dışı alanı su olarak kabul ediyoruz.
Çözüm:
Ada sayısını tutmak için bir değişkeni 0 değeriyle ilklendiriyoruz.
Array'i başından sonuna döngülüyoruz. Eğer '1' değerine denk gelirsek ada sayısını 1 arttırıyoruz. Bu değerine olası 4 tarafına depth first search gönderiyoruz. Eğer bunlardan birinde '1' değerine denk gelirsek bunu '0' yapıyoruz, böylece aynı yerden tekrar işlem yapmayız. Ondan sonra eğer '1' değerine denk gelmişsek yine bunun 4 tarafına DFS gönderiyoruz. Bu DFS işlemiyle bir adanın tüm değerlerini '0' yapıp, bir daha bu aynı ada üzerinde bulunan '1' değerine denk gelmiyoruz. Bu işlemler ile array'i dögüleyerek adalar sayısını buluyoruz.
Kod:
public int numIslands(char[][]grid)
{
int count = 0;
for(int i = 0; i<grid.length; i++)
{
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == '1')
{
count++;
grid[i][j] = '0';
gridDFS(grid, i, j);
}
}
}
return count;
}
static void gridDFS(char [][] grid, int i, int j)
{
if(grid[i][j] == '0')
{
return;
}
grid[i][j] = '0';
if(i > 0)
{
gridDFS(grid, i-1, j);
}
if(i < grid.length-1)
{
gridDFS(grid, i+1, j);
}
if (j > 0) {
gridBFS(grid, i, j-1);
}
if(j < grid[i].length-1)
{
gridDFS(grid, i, j+1);
}
}
Bunun daha ileri verisyonu: 694. Number of Distinct Islands