202402112020
tags: #dfs

class Solution:
	def numIslands(self, grid: List[List[str]]) -> int:
		m, n = len(grid), len(grid[0])
		res = 0
		dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		def dfs(i, j):
			grid[i][j] = "0"
			for dir in dirs:
				dx = i + dir[0]
				dy = j + dir[1]
				if 0 <= dx < m and 0 <= dy < n and grid[dx][dy] == "1":
					dfs(dx, dy)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == "1":
					dfs(i, j)
					res += 1
		return res

Reference

https://leetcode.com/problems/number-of-islands/