मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। हमें इसमें द्वीपों की संख्या गिननी है। एक द्वीप वह स्थान है जो पानी से घिरा होता है और आसन्न भूमि को क्षैतिज या लंबवत रूप से जोड़कर बनता है। हम मान सकते हैं कि ग्रिड के चारों किनारे पानी से घिरे हैं।
मान लीजिए कि ग्रिड इस तरह है -
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
तीन द्वीप हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
दो तरीके होंगे, एक का उपयोग numIslands() और makeWater() नामक द्वीपों की संख्या गिनने के लिए किया जाएगा। मेकवाटर () इस तरह होगा -
-
यदि ग्रिड में पंक्तियों की संख्या 0 है, तो 0 पर लौटें
-
n =पंक्ति गणना और m :=स्तंभ संख्या, और उत्तर :=0
-
मेरे लिए 0 से n - 1 की सीमा में
-
j के लिए 0 से m की सीमा में
-
अगर ग्रिड [i, j] =1, तो उत्तर:=उत्तर + 1
-
मेकवाटर (i, j, n, m, ग्रिड)
-
-
-
मेकवाटर () इंडेक्स i, j, रो और कॉल काउंट n और m, और ग्रिड लेगा
-
अगर मैं <0 या j <0 या i>=n या j>=m, तो इस विधि से वापस आएं
-
अगर ग्रिड [i, j] =0, तो वापस लौटें अन्यथा ग्रिड बनाएं [i, j]:=0
-
मेकवाटर (i + 1, j, n, m, ग्रिड) पर कॉल करें
-
मेकवाटर (i, j + 1, n, m, ग्रिड) पर कॉल करें
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ if len(grid) == 0: return 0 n= len(grid) m = len(grid[0]) ans = 0 for i in range(n): for j in range(m): if grid[i][j] == "1": ans+=1 self.make_water(i,j,n,m,grid) return ans def make_water(self,i,j,n,m,grid): if i<0 or j<0 or i>=n or j>=m: return if grid[i][j] == "0": return else: grid[i][j]="0" self.make_water(i+1,j,n,m,grid) self.make_water(i,j+1,n,m,grid) self.make_water(i-1,j,n,m,grid) self.make_water(i,j-1,n,m,grid)
इनपुट
[["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]
आउटपुट
3