রৈখিক 2d গ্রিড মানচিত্র স্ক্যান করুন, যদি একটি নোডে '1' থাকে, তাহলে এটি একটি রুট নোড যা একটি গভীরতার প্রথম অনুসন্ধানকে ট্রিগার করে। DFS চলাকালীন, ভিজিট করা নোড হিসেবে চিহ্নিত করতে প্রতিটি ভিজিট করা নোডকে '0' হিসেবে সেট করা উচিত। DFS ট্রিগারকারী রুট নোডের সংখ্যা গণনা করুন, এই সংখ্যাটি হবে দ্বীপের সংখ্যা যেহেতু প্রতিটি DFS কিছু রুট থেকে শুরু করে একটি দ্বীপকে চিহ্নিত করে।
উদাহরণ
using System;
namespace ConsoleApplication{
public class Matrix{
public int PrintNumberOfIslands(char[,] grid){
bool[,] visited = new bool[grid.GetLength(0), grid.GetLength(1)];
int res = 0;
for (int i = 0; i < grid.GetLength(0); i++){
for (int j = 0; j < grid.GetLength(1); j++){
if (grid[i, j] == '1' && !visited[i, j]){
DFS(grid, visited, i, j);
res++;
}
}
}
return res;
}
public void DFS(char[,] grid, bool[,] visited, int i, int j){
if (i < 0 || i >= grid.GetLength(0)) return;
if (j < 0 || j >= grid.GetLength(1)) return;
if (grid[i, j] != '1' || visited[i, j]) return;
visited[i, j] = true;
DFS(grid, visited, i + 1, j);
DFS(grid, visited, i - 1, j);
DFS(grid, visited, i, j + 1);
DFS(grid, visited, i, j - 1);
}
}
class Program{
static void Main(string[] args){
Matrix m = new Matrix();
char[,] mm = { { '1', '1', '1', '1', '0' }, { '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' }, { '0', '0', '0', '0', '1' } };
Console.WriteLine(m.PrintNumberOfIslands(mm));
}
}
} আউটপুট
2
