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
