Given a grid of size n*m (n is the number of rows and m is the number of columns in the grid) consisting of '0's (Water) and '1's(Land). Find the number of islands.
Note: An island is either surrounded by water or boundary of grid and is formed by connecting adjacent lands horizontally or vertically or diagonally i.e., in all 8 directions.
Example 1:
Input:
grid = {{0,1},{1,0},{1,1},{1,0}}
Output:
1
Explanation:
The grid is-
0 1
1 0
1 1
1 0
All lands are connected.
Example 2:
Input:
grid = {{0,1,1,1,0,0,0},{0,0,1,1,0,1,0}}
Output:
2
Expanation:
The grid is-
0 1 1 1 0 0 0
0 0 1 1 0 1 0 
There are two islands :- one is colored in blue 
and other in orange.
Your Task:
You don't need to read or print anything. Your task is to complete the function numIslands() which takes the grid as an input parameter and returns the total number of islands.
Expected Time Complexity: O(n*m)
Expected Space Complexity: O(n*m)
Constraints:
1 ≤ n, m ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



import sys

sys.setrecursionlimit(10**8)

class Solution:

    def numIslands(self,grid):

        #code here

Solutions:
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		(m, n) = (len(grid), len(grid[0]))

		def dfs(row, col):
			if row < 0 or row >= m or col < 0 or (col >= n):
				return
			if grid[row][col] == 1:
				grid[row][col] = 0
				dfs(row + 1, col)
				dfs(row, col + 1)
				dfs(row - 1, col)
				dfs(row, col - 1)
				dfs(row + 1, col + 1)
				dfs(row - 1, col - 1)
				dfs(row - 1, col + 1)
				dfs(row + 1, col - 1)
		res = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					res += 1
					dfs(i, j)
		return res


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		visted = set()
		count = 0
		N = len(grid)
		M = len(grid[0])
		for i in range(N):
			for j in range(M):
				if (i, j) not in visted and grid[i][j] == 1:
					self.F = 1
					self.Dfs(grid, i, j, visted, N, M)
					count += 1
		return count

	def Edge(self, mat, i, j, N, M):
		if i == 0 or j == 0 or i == N - 1 or (j == M - 1):
			return True
		return False

	def safe(self, x, y, gp):
		if x >= 0 and x < len(gp) and (y >= 0) and (y < len(gp[0])) and (gp[x][y] == 1):
			return True
		return False

	def Dfs(self, mat, i, j, visted, N, M):
		visted.add((i, j))
		if self.Edge(mat, i, j, N, M):
			self.F = 0
		List = [(1, 0), (0, 1), (0, -1), (-1, 0), (1, -1), (1, 1), (-1, 1), (-1, -1)]
		for (a, b) in List:
			if self.safe(i + a, j + b, mat) == True and (i + a, j + b) not in visted:
				self.Dfs(mat, i + a, j + b, visted, N, M)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def util(self, a, i, j, n, m):
		if i >= n or j >= m or i < 0 or (j < 0) or (a[i][j] == 0):
			return
		a[i][j] = 0
		self.util(a, i + 1, j, n, m)
		self.util(a, i - 1, j, n, m)
		self.util(a, i, j + 1, n, m)
		self.util(a, i, j - 1, n, m)
		self.util(a, i + 1, j + 1, n, m)
		self.util(a, i - 1, j - 1, n, m)
		self.util(a, i + 1, j - 1, n, m)
		self.util(a, i - 1, j + 1, n, m)

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					count += 1
					self.util(grid, i, j, n, m)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def bfsOnMatrix(V, grid):
			queue = []
			queue.append(V)
			while len(queue) > 0:
				temp = queue.pop(0)
				for i in range(-1, 2):
					for j in range(-1, 2):
						xIndex = i + temp[0]
						yIndex = j + temp[1]
						if xIndex >= 0 and xIndex < len(grid) and (yIndex >= 0) and (yIndex < len(grid[0])) and (grid[xIndex][yIndex] == 1):
							if visited[xIndex][yIndex] == 0:
								queue.append((xIndex, yIndex))
								visited[xIndex][yIndex] = 1
		c = 0
		visited = []
		for i in range(0, len(grid)):
			temp = []
			for j in range(0, len(grid[0])):
				temp.append(0)
			visited.append(temp)
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if visited[i][j] == 0 and grid[i][j] == 1:
					visited[i][j] = 1
					c = c + 1
					bfsOnMatrix((i, j), grid)
		return c


import sys
from collections import deque
sys.setrecursionlimit(10 ** 8)

def isSafe(grid, i, j, visited):
	return i >= 0 and i < len(grid) and (j >= 0) and (j < len(grid[0])) and (grid[i][j] and (not visited[i][j]))

def BFS(grid, si, sj, visited):
	row = [-1, -1, -1, 0, 0, 1, 1, 1]
	column = [-1, 0, 1, -1, 1, -1, 0, 1]
	q = deque()
	q.append([si, sj])
	visited[si][sj] = True
	while len(q) > 0:
		temp = q.popleft()
		i = temp[0]
		j = temp[1]
		for k in range(8):
			if isSafe(grid, i + row[k], j + column[k], visited):
				visited[i + row[k]][j + column[k]] = True
				q.append((i + row[k], j + column[k]))

class Solution:

	def numIslands(self, grid):
		visited = [[False for i in range(m)] for j in range(n)]
		islands = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] and (not visited[i][j]):
					BFS(grid, i, j, visited)
					islands += 1
		return islands


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		islands = 0
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] == 1:
					islands += 1
					self.dfs(grid, r, c)
		return islands

	def dfs(self, grid, row, col):
		for r in range(row - 1, row + 2):
			for c in range(col - 1, col + 2):
				if r >= 0 and r < len(grid) and (c >= 0) and (c < len(grid[0])):
					if grid[r][c] == 1:
						grid[r][c] = 0
						self.dfs(grid, r, c)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		return find_islands(grid)
grid = [[0, 1, 1, 1, 0, 0, 0], [0, 0, 1, 1, 0, 1, 0]]

def find_neighbours(i, j, m, n):
	neighbours = []
	if i > 0:
		neighbours.append((i - 1, j))
		if j > 0:
			neighbours.append((i - 1, j - 1))
		if j < m - 1:
			neighbours.append((i - 1, j + 1))
	if j > 0:
		neighbours.append((i, j - 1))
	if j < m - 1:
		neighbours.append((i, j + 1))
	if i < n - 1:
		neighbours.append((i + 1, j))
		if j > 0:
			neighbours.append((i + 1, j - 1))
		if j < m - 1:
			neighbours.append((i + 1, j + 1))
	return neighbours

def find_islands(G):

	def visit(G, i, j, visited):
		visited[i][j] = True
		for neighbour in find_neighbours(i, j, m, n):
			if G[neighbour[0]][neighbour[1]] == 1 and visited[neighbour[0]][neighbour[1]] == False:
				visit(G, neighbour[0], neighbour[1], visited)
	n = len(G)
	m = len(G[0])
	visited = [[False for j in range(m)] for i in range(n)]
	count = 0
	for i in range(n):
		for j in range(m):
			if G[i][j] == 1 and visited[i][j] == False:
				visit(G, i, j, visited)
				count += 1
	return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def bfs(visited, row, col, grid):
			n = len(grid)
			m = len(grid[0])
			visited[row][col] = 1
			q = []
			q.append([row, col])
			while q:
				row = q[0][0]
				col = q[0][1]
				q.pop(0)
				for i in range(-1, 2, 1):
					for j in range(-1, 2, 1):
						nrow = row + i
						ncol = col + j
						if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] != 1) and (grid[nrow][ncol] == 1):
							visited[nrow][ncol] = 1
							q.append([nrow, ncol])
		n = len(grid)
		m = len(grid[0])
		c = 0
		visited = [[0] * m for i in grid]
		for row in range(n):
			for col in range(m):
				if visited[row][col] != 1 and grid[row][col] == 1:
					c += 1
					bfs(visited, row, col, grid)
		return c


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfsTraversal(self, grid, isVisited, i, j, m, n):
		if isVisited[i][j]:
			return
		isVisited[i][j] = 1
		if i - 1 >= 0:
			if grid[i - 1][j]:
				self.dfsTraversal(grid, isVisited, i - 1, j, m, n)
			if j - 1 >= 0 and grid[i - 1][j - 1]:
				self.dfsTraversal(grid, isVisited, i - 1, j - 1, m, n)
			if j + 1 < n and grid[i - 1][j + 1]:
				self.dfsTraversal(grid, isVisited, i - 1, j + 1, m, n)
		if i + 1 < m:
			if grid[i + 1][j]:
				self.dfsTraversal(grid, isVisited, i + 1, j, m, n)
			if j - 1 >= 0 and grid[i + 1][j - 1]:
				self.dfsTraversal(grid, isVisited, i + 1, j - 1, m, n)
			if j + 1 < n and grid[i + 1][j + 1]:
				self.dfsTraversal(grid, isVisited, i + 1, j + 1, m, n)
		if j - 1 >= 0 and grid[i][j - 1]:
			self.dfsTraversal(grid, isVisited, i, j - 1, m, n)
		if j + 1 < n and grid[i][j + 1]:
			self.dfsTraversal(grid, isVisited, i, j + 1, m, n)

	def numIslands(self, grid):
		m = len(grid)
		n = len(grid[0])
		isVisited = [[0 for j in range(n)] for i in range(m)]
		res = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] and (not isVisited[i][j]):
					self.dfsTraversal(grid, isVisited, i, j, m, n)
					res += 1
		return res


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		global n
		global m
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for c in range(m)] for r in range(n)]
		ops = [[1, -1], [1, 0], [1, 1], [0, -1], [0, 1], [-1, -1], [-1, 0], [-1, 1]]

		def dfs(r, c):
			if r < 0 or c < 0 or r >= n or (c >= m):
				return
			elif vis[r][c] == 1:
				return
			elif grid[r][c] == 0:
				vis[r][c] = 1
				return
			else:
				vis[r][c] = 1
				for (i, j) in ops:
					dfs(r + i, c + j)
		cnt = 0
		for r in range(n):
			for c in range(m):
				if grid[r][c] == 1 and vis[r][c] == 0:
					cnt += 1
					dfs(r, c)
		return cnt


import sys
sys.setrecursionlimit(10 ** 8)
import itertools
from collections import deque

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[None for _ in range(m)] for _ in range(n)]

		def dfs(row, col):
			visited[row][col] = 1
			for delRow in range(-1, 2):
				for delCol in range(-1, 2):
					nRow = delRow + row
					nCol = delCol + col
					if nRow >= 0 and nRow < n and (nCol >= 0) and (nCol < m) and (grid[nRow][nCol] == 1) and (visited[nRow][nCol] == None):
						dfs(nRow, nCol)
		count = 0
		for (row, col) in itertools.product(range(n), range(m)):
			if visited[row][col] == None and grid[row][col] == 1:
				count += 1
				dfs(row, col)
		return count


import sys
sys.setrecursionlimit(10 ** 8)
import itertools
from collections import deque

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[None for _ in range(m)] for _ in range(n)]

		def bfs(row, col):
			q = deque()
			visited[row][col] = 1
			q.append((row, col))
			while q:
				(newRow, newCol) = q.popleft()
				for delRow in range(-1, 2):
					for delCol in range(-1, 2):
						nRow = newRow + delRow
						nCol = newCol + delCol
						if nRow >= 0 and nRow < n and (nCol >= 0) and (nCol < m) and (grid[nRow][nCol] == 1) and (visited[nRow][nCol] == None):
							visited[nRow][nCol] = 1
							q.append((nRow, nCol))
		count = 0
		for (row, col) in itertools.product(range(n), range(m)):
			if visited[row][col] == None and grid[row][col] == 1:
				count += 1
				bfs(row, col)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		visit = set()
		res = 0

		def dfs(r, c):
			if r < 0 or c < 0 or r >= rows or (c >= cols) or ((r, c) in visit) or (grid[r][c] != 1):
				return
			visit.add((r, c))
			dfs(r + 1, c)
			dfs(r - 1, c)
			dfs(r, c + 1)
			dfs(r, c - 1)
			dfs(r - 1, c - 1)
			dfs(r - 1, c + 1)
			dfs(r + 1, c - 1)
			dfs(r + 1, c + 1)
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 1 and (i, j) not in visit:
					dfs(i, j)
					res += 1
		return res


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, i, j, n, m, grid, visited):
		visited[i][j] = True
		dr = [-1, -1, -1, 0, 1, 1, 1, 0]
		dc = [-1, 0, 1, 1, 1, 0, -1, -1]
		for k in range(8):
			r = i + dr[k]
			c = j + dc[k]
			if r >= 0 and c >= 0 and (r < n) and (c < m) and (not visited[r][c]) and grid[r][c]:
				self.dfs(r, c, n, m, grid, visited)

	def numIslands(self, grid):
		(res, n, m) = (0, len(grid), len(grid[0]))
		visited = [[False for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if not visited[i][j] and grid[i][j]:
					self.dfs(i, j, n, m, grid, visited)
					res += 1
		return res


import sys
sys.setrecursionlimit(10 ** 8)
from queue import Queue

class Solution:

	def numIslands(self, grid):
		vis = set()
		s = Queue()
		row_Dir = [-1, -1, 0, 1, 1, 1, 0, -1]
		col_Dir = [0, -1, -1, -1, 0, 1, 1, 1]
		cnt = 0
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (i, j) not in vis:
					cnt += 1
					s.put([i, j])
					vis.add((i, j))
					while not s.empty():
						curr = s.get()
						currRow = curr[0]
						currCol = curr[1]
						for dir in range(8):
							dRow = row_Dir[dir] + currRow
							dCol = col_Dir[dir] + currCol
							if dRow >= 0 and dRow < n and (dCol >= 0) and (dCol < m) and (grid[dRow][dCol] == 1) and ((dRow, dCol) not in vis):
								s.put([dRow, dCol])
								vis.add((dRow, dCol))
		return cnt


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		i = 0
		j = 0
		number_island = []
		visited = [[False for i in range(len(grid[0]))] for j in range(len(grid))]
		island = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (not visited[i][j]):
					visited[i][j] = True
					island = island + 1
					self.find_connected_island(i, j, visited, grid)
		return island

	def find_connected_island(self, i, j, visited, grid):
		if j > 0 and grid[i][j - 1] == 1 and (not visited[i][j - 1]):
			visited[i][j - 1] = True
			self.find_connected_island(i, j - 1, visited, grid)
		if j < len(grid[0]) - 1 and grid[i][j + 1] == 1 and (not visited[i][j + 1]):
			visited[i][j + 1] = True
			self.find_connected_island(i, j + 1, visited, grid)
		if i > 0 and grid[i - 1][j] == 1 and (not visited[i - 1][j]):
			visited[i - 1][j] = True
			self.find_connected_island(i - 1, j, visited, grid)
		if i < len(grid) - 1 and grid[i + 1][j] == 1 and (not visited[i + 1][j]):
			visited[i + 1][j] = True
			self.find_connected_island(i + 1, j, visited, grid)
		if i > 0 and j > 0 and (grid[i - 1][j - 1] == 1) and (not visited[i - 1][j - 1]):
			visited[i - 1][j - 1] = True
			self.find_connected_island(i - 1, j - 1, visited, grid)
		if i > 0 and j < len(grid[0]) - 1 and (grid[i - 1][j + 1] == 1) and (not visited[i - 1][j + 1]):
			visited[i - 1][j + 1] = True
			self.find_connected_island(i - 1, j + 1, visited, grid)
		if i < len(grid) - 1 and j > 0 and (grid[i + 1][j - 1] == 1) and (not visited[i + 1][j - 1]):
			visited[i + 1][j - 1] = True
			self.find_connected_island(i + 1, j - 1, visited, grid)
		if i < len(grid) - 1 and j < len(grid[0]) - 1 and (grid[i + 1][j + 1] == 1) and (not visited[i + 1][j + 1]):
			visited[i + 1][j + 1] = True
			self.find_connected_island(i + 1, j + 1, visited, grid)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		ic = 0
		r = len(grid)
		c = len(grid[0])

		def dfs(i, j):
			if i < 0 or j < 0 or i >= r or (j >= c) or (grid[i][j] != 1):
				return
			grid[i][j] = -1
			dfs(i - 1, j)
			dfs(i - 1, j + 1)
			dfs(i, j + 1)
			dfs(i + 1, j + 1)
			dfs(i + 1, j)
			dfs(i + 1, j - 1)
			dfs(i, j - 1)
			dfs(i - 1, j - 1)
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					ic += 1
					dfs(i, j)
		return ic


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def validboundaries(self, n, m, x, y):
		if n >= 0 and n < x and (m >= 0) and (m < y):
			return True
		return False

	def checkBoundaries(self, grid, n, m, x, y):
		if self.validboundaries(n, m + 1, x, y):
			if grid[n][m + 1] == 1:
				grid[n][m + 1] = 0
				self.checkBoundaries(grid, n, m + 1, x, y)
		if self.validboundaries(n + 1, m - 1, x, y):
			if grid[n + 1][m - 1] == 1:
				grid[n + 1][m - 1] = 0
				self.checkBoundaries(grid, n + 1, m - 1, x, y)
		if self.validboundaries(n + 1, m, x, y):
			if grid[n + 1][m] == 1:
				grid[n + 1][m] = 0
				self.checkBoundaries(grid, n + 1, m, x, y)
		if self.validboundaries(n + 1, m + 1, x, y):
			if grid[n + 1][m + 1] == 1:
				grid[n + 1][m + 1] = 0
				self.checkBoundaries(grid, n + 1, m + 1, x, y)
		if self.validboundaries(n - 1, m - 1, x, y):
			if grid[n - 1][m - 1] == 1:
				grid[n - 1][m - 1] = 0
				self.checkBoundaries(grid, n - 1, m - 1, x, y)
		if self.validboundaries(n - 1, m, x, y):
			if grid[n - 1][m] == 1:
				grid[n - 1][m] = 0
				self.checkBoundaries(grid, n - 1, m, x, y)
		if self.validboundaries(n - 1, m + 1, x, y):
			if grid[n - 1][m + 1] == 1:
				grid[n - 1][m + 1] = 0
				self.checkBoundaries(grid, n - 1, m + 1, x, y)
		if self.validboundaries(n, m - 1, x, y):
			if grid[n][m - 1] == 1:
				grid[n][m - 1] = 0
				self.checkBoundaries(grid, n, m - 1, x, y)
		return

	def numIslands(self, grid):
		count = 0
		x = len(grid)
		y = len(grid[0])
		for n in range(x):
			for m in range(y):
				if grid[n][m] == 1:
					count += 1
					grid[n][m] = 0
					self.checkBoundaries(grid, n, m, x, y)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

def count_island(grid, i, j, x, y):
	if i < 0 or i >= x or j < 0 or (j >= y) or (grid[i][j] != 1):
		return
	grid[i][j] = 2
	count_island(grid, i + 1, j, x, y)
	count_island(grid, i + 1, j + 1, x, y)
	count_island(grid, i - 1, j, x, y)
	count_island(grid, i - 1, j - 1, x, y)
	count_island(grid, i, j + 1, x, y)
	count_island(grid, i, j - 1, x, y)
	count_island(grid, i + 1, j - 1, x, y)
	count_island(grid, i - 1, j + 1, x, y)

class Solution:

	def numIslands(self, grid):
		(x, y) = (len(grid), len(grid[0]))
		islands = 0
		for i in range(x):
			for j in range(y):
				if grid[i][j] == 1:
					count_island(grid, i, j, x, y)
					islands += 1
		return islands


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def dfs(i, j, queue):
			queue.append([i, j])
			while len(queue) > 0:
				(e1, e2) = queue.pop()
				grid[e1][e2] = 0
				dirx = [-1, -1, -1, 0, 0, 1, 1, 1]
				diry = [-1, 0, 1, -1, 1, -1, 0, 1]
				for ele in range(8):
					newx = e1 + dirx[ele]
					newy = e2 + diry[ele]
					if 0 <= newx <= len(grid) - 1 and 0 <= newy <= len(grid[0]) - 1 and grid[newx][newy]:
						queue.append([newx, newy])
		count = 0
		queue = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j]:
					count += 1
					dfs(i, j, queue)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, grid, i, j, visited):
		if (i, j) not in visited and grid[i][j] == 1:
			visited.add((i, j))
			for x in [0, 1, -1]:
				for y in [0, 1, -1]:
					if not x and (not y):
						continue
					if i + x >= 0 and i + x < len(grid) and (j + y >= 0) and (j + y < len(grid[0])):
						self.dfs(grid, i + x, j + y, visited)

	def numIslands(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visited = set()
		islands = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] and (i, j) not in visited:
					self.dfs(grid, i, j, visited)
					islands += 1
		return islands


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def bfs(grid, visit, q, i, j):
			q.append([i, j])
			visit[i][j] = 1
			while len(q):
				p = q.popleft()
				k = p[0]
				l = p[1]
				for a in range(-1, 2):
					for b in range(-1, 2):
						row = a + k
						col = b + l
						if row >= 0 and col >= 0 and (row < len(grid)) and (col < len(grid[0])) and (visit[row][col] == 0) and (grid[row][col] == 1):
							visit[row][col] = 1
							q.append([row, col])
		visit = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
		c = 0
		q = deque()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visit[i][j] == 0 and grid[i][j] == 1:
					bfs(grid, visit, q, i, j)
					c += 1
		return c


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def _dfsnode(self, i, j):
		if self.visited[i][j]:
			return
		self.visited[i][j] = True
		for x in [-1, 0, 1]:
			for y in [-1, 0, 1]:
				neighbour_x = j + x
				neighbour_y = i + y
				if neighbour_x < self.columns and neighbour_x > -1 and (neighbour_y < self.rows) and (neighbour_y > -1):
					if self.grid[neighbour_y][neighbour_x]:
						self._dfsnode(neighbour_y, neighbour_x)
		return

	def numIslands(self, grid):
		self.grid = grid
		self.columns = len(grid[0])
		self.rows = len(grid)
		self.visited = []
		islands = 0
		for i in range(self.rows):
			row = []
			for j in range(self.columns):
				row.append(False)
			self.visited.append(row)
		for i in range(self.rows):
			for j in range(self.columns):
				if not self.visited[i][j]:
					if self.grid[i][j]:
						islands += 1
						self._dfsnode(i, j)
		return islands


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		row = len(grid)
		col = len(grid[0])
		visited = []
		for i in range(0, row + 1):
			ax = [False] * (col + 1)
			visited.append(ax)
		row1 = [-1, -1, -1, 0, 0, 1, 1, 1]
		col1 = [-1, 0, 1, -1, 1, -1, 0, 1]

		def dfs(visited, grid, i, j):
			visited[i][j] = True
			for k in range(0, 8):
				rowfin = i + row1[k]
				colfin = j + col1[k]
				if rowfin > -1 and rowfin < row and (colfin > -1) and (colfin < col) and (visited[rowfin][colfin] == False) and (grid[rowfin][colfin] == 1):
					dfs(visited, grid, rowfin, colfin)
					visited[rowfin][colfin] = True
		finalans = 0
		for i in range(0, row):
			for j in range(0, col):
				if visited[i][j] == False and grid[i][j] == 1:
					dfs(visited, grid, i, j)
					finalans += 1
		return finalans


import sys
sys.setrecursionlimit(10 ** 8)

def check_limit(grid, i, j):
	n = len(grid)
	m = len(grid[0])
	if i >= 0 and j >= 0 and (i < n) and (j < m):
		return True
	else:
		return False

def mark_island(grid, i, j, visited):
	if check_limit(grid, i, j):
		if grid[i][j] == 1 and visited[i][j] != 1:
			visited[i][j] = 1
			mark_island(grid, i + 1, j + 1, visited)
			mark_island(grid, i - 1, j - 1, visited)
			mark_island(grid, i + 1, j, visited)
			mark_island(grid, i, j + 1, visited)
			mark_island(grid, i - 1, j, visited)
			mark_island(grid, i, j - 1, visited)
			mark_island(grid, i + 1, j - 1, visited)
			mark_island(grid, i - 1, j + 1, visited)
		else:
			return

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		count = 0
		visited = [[None for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and visited[i][j] != 1:
					count += 1
					mark_island(grid, i, j, visited)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		m = len(grid)
		n = len(grid[0])

		def dfs(r, c):
			if r < 0 or c < 0 or r >= m or (c >= n) or (grid[r][c] != 1) or ((r, c) in visited):
				return
			visited.add((r, c))
			dfs(r - 1, c - 1)
			dfs(r - 1, c)
			dfs(r - 1, c + 1)
			dfs(r, c - 1)
			dfs(r, c + 1)
			dfs(r + 1, c - 1)
			dfs(r + 1, c)
			dfs(r + 1, c + 1)
		count = 0
		visited = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if (i, j) not in visited and grid[i][j] == 1:
					count += 1
					dfs(i, j)
		return count


from queue import Queue

class Solution:

	def bfs(self, grid, i, j, n, m):
		q = Queue()
		q.put((i, j))
		directions = ((-1, 0), (1, 0), (0, 1), (0, -1), (-1, -1), (-1, 1), (1, -1), (1, 1))
		grid[i][j] = 0
		while not q.empty():
			(x, y) = q.get()
			for dir in directions:
				(dx, dy) = dir
				if x + dx < 0 or y + dy < 0 or x + dx >= n or (y + dy >= m) or (grid[x + dx][y + dy] == 0):
					continue
				q.put((x + dx, y + dy))
				grid[x + dx][y + dy] = 0

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		c = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					self.bfs(grid, i, j, n, m)
					c += 1
		return c


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, a, i, j):
		for k in range(-1, 2):
			for l in range(-1, 2):
				row = i + k
				col = j + l
				if row >= 0 and col >= 0 and (row < len(a)) and (col < len(a[0])) and (a[row][col] == 1):
					a[row][col] = 2
					self.dfs(a, row, col)

	def numIslands(self, a):
		n = len(a)
		m = len(a[0])
		ans = 0
		for i in range(n):
			for j in range(m):
				if a[i][j] == 1:
					a[i][j] = 2
					ans += 1
					self.dfs(a, i, j)
		return ans


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, grid, i, j):
		if i >= 0 and i < len(grid) and (j >= 0) and (j < len(grid[0])) and (grid[i][j] == 1):
			grid[i][j] = 0
			self.dfs(grid, i - 1, j + 1)
			self.dfs(grid, i - 1, j - 1)
			self.dfs(grid, i - 1, j)
			self.dfs(grid, i + 1, j + 1)
			self.dfs(grid, i + 1, j - 1)
			self.dfs(grid, i + 1, j)
			self.dfs(grid, i, j + 1)
			self.dfs(grid, i, j - 1)

	def numIslands(self, grid):
		res = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					res += 1
					self.dfs(grid, i, j)
		return res


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for _ in range(m)] for _ in range(n)]
		cnt = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					cnt += 1
					self.bfs(i, j, grid, vis, n, m)
		return cnt

	def bfs(self, r, c, grid, vis, n, m):
		q = [(r, c)]
		vis[r][c] = 1
		while q:
			(newr, newc) = q.pop(0)
			for row in [-1, 0, 1]:
				for col in [-1, 0, 1]:
					nrow = row + newr
					ncol = col + newc
					if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (grid[nrow][ncol] == 1) and (vis[nrow][ncol] == 0):
						vis[nrow][ncol] = 1
						q.append((nrow, ncol))


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		self.row_len = len(grid)
		self.col_len = len(grid[0])
		i = j = 0
		no_of_islands = 0
		while i < self.row_len:
			j = 0
			while j < self.col_len:
				if grid[i][j] == 1:
					self.find_island(grid, i, j)
					no_of_islands = no_of_islands + 1
				j = j + 1
			i = i + 1
		return no_of_islands

	def find_island(self, grid, x, y):
		if not self.is_under_limit(x, y):
			return
		if grid[x][y] != 1:
			return
		grid[x][y] = -1
		self.find_island(grid, x + 1, y)
		self.find_island(grid, x - 1, y)
		self.find_island(grid, x, y + 1)
		self.find_island(grid, x, y - 1)
		self.find_island(grid, x - 1, y - 1)
		self.find_island(grid, x - 1, y + 1)
		self.find_island(grid, x + 1, y + 1)
		self.find_island(grid, x + 1, y - 1)

	def is_under_limit(self, x, y):
		return x >= 0 and x != self.row_len and (y >= 0) and (y != self.col_len)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		if not grid:
			return 0
		num_rows = len(grid)
		num_cols = len(grid[0])
		count = 0

		def dfs(row, col):
			if row < 0 or row >= num_rows or col < 0 or (col >= num_cols) or (grid[row][col] != 1):
				return
			grid[row][col] = 0
			dfs(row - 1, col)
			dfs(row + 1, col)
			dfs(row, col - 1)
			dfs(row, col + 1)
			dfs(row - 1, col - 1)
			dfs(row - 1, col + 1)
			dfs(row + 1, col - 1)
			dfs(row + 1, col + 1)
		for row in range(num_rows):
			for col in range(num_cols):
				if grid[row][col] == 1:
					dfs(row, col)
					count += 1
		return count


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		r = len(grid)
		c = len(grid[0])

		def dfs(ro, co, grid):
			q = deque()
			q.append((ro, co))
			grid[ro][co] = 0
			while q:
				(row, col) = q.popleft()
				X = [0, 1, 0, -1, -1, 1, -1, 1]
				Y = [1, 0, -1, 0, -1, 1, 1, -1]
				for (dr, dc) in zip(X, Y):
					nro = row + dr
					nco = col + dc
					if nro in range(r) and nco in range(c) and (nro, nco) and (grid[nro][nco] == 1):
						q.append((nro, nco))
						grid[nro][nco] = 0
		islands = 0
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					islands += 1
					dfs(i, j, grid)
		return islands


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def check(i, j, r, c):
			if i >= 0 and j >= 0 and (i < r) and (j < c):
				return True
			else:
				return False

		def recur(grid, i, j, r, c):
			if check(i, j, r, c) == False:
				return
			if grid[i][j] == 1:
				grid[i][j] = 0
				recur(grid, i, j - 1, r, c)
				recur(grid, i - 1, j, r, c)
				recur(grid, i, j + 1, r, c)
				recur(grid, i + 1, j, r, c)
				recur(grid, i - 1, j - 1, r, c)
				recur(grid, i - 1, j + 1, r, c)
				recur(grid, i + 1, j - 1, r, c)
				recur(grid, i + 1, j + 1, r, c)
		r = len(grid)
		c = len(grid[0])
		cnt = 0
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					recur(grid, i, j, r, c)
					cnt += 1
		return cnt


import sys
sys.setrecursionlimit(10 ** 8)
from collections import deque

class Solution:

	def bfs(self, row, col, visited, grid):
		(n, m) = (len(grid), len(grid[0]))
		q = deque()
		q.append((row, col))
		visited[row][col] = 1
		while q:
			(row, col) = q.popleft()
			if row - 1 >= 0 and grid[row - 1][col] == 1 and (visited[row - 1][col] == -1):
				visited[row - 1][col] = 1
				q.append((row - 1, col))
			if row - 1 >= 0 and col - 1 >= 0 and (grid[row - 1][col - 1] == 1) and (visited[row - 1][col - 1] == -1):
				visited[row - 1][col - 1] = 1
				q.append((row - 1, col - 1))
			if row - 1 >= 0 and col + 1 < m and (grid[row - 1][col + 1] == 1) and (visited[row - 1][col + 1] == -1):
				visited[row - 1][col + 1] = 1
				q.append((row - 1, col + 1))
			if row + 1 < n and grid[row + 1][col] == 1 and (visited[row + 1][col] == -1):
				visited[row + 1][col] = 1
				q.append((row + 1, col))
			if row + 1 < n and col - 1 >= 0 and (grid[row + 1][col - 1] == 1) and (visited[row + 1][col - 1] == -1):
				visited[row + 1][col - 1] = 1
				q.append((row + 1, col - 1))
			if row + 1 < n and col + 1 < m and (grid[row + 1][col + 1] == 1) and (visited[row + 1][col + 1] == -1):
				visited[row + 1][col + 1] = 1
				q.append((row + 1, col + 1))
			if col - 1 >= 0 and grid[row][col - 1] == 1 and (visited[row][col - 1] == -1):
				visited[row][col - 1] = 1
				q.append((row, col - 1))
			if col + 1 < m and grid[row][col + 1] == 1 and (visited[row][col + 1] == -1):
				visited[row][col + 1] = 1
				q.append((row, col + 1))

	def numIslands(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visited = [[-1 for _ in range(m)] for _ in range(n)]
		cnt = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and visited[i][j] == -1:
					self.bfs(i, j, visited, grid)
					cnt += 1
		return cnt


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isSafe(self, x, y, n, m):
		return x >= 0 and x < n and (y >= 0) and (y < m)

	def dfs(self, i, j, grid, n, m, visited):
		visited[i][j] = 1
		d_x = [-1, -1, -1, 0, 0, 1, 1, 1]
		d_y = [-1, 0, 1, -1, 1, -1, 0, 1]
		for k in range(8):
			x = i + d_x[k]
			y = j + d_y[k]
			if self.isSafe(x, y, n, m) and (not visited[x][y]) and grid[x][y]:
				self.dfs(x, y, grid, n, m, visited)

	def numIslands(self, grid):
		count = 0
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if not visited[i][j] and grid[i][j]:
					count += 1
					self.dfs(i, j, grid, n, m, visited)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

def find_number_of_island(grid: [[]]):
	max_row = len(grid) - 1
	max_col = len(grid[0]) - 1
	visited = [[False] * (max_col + 1) for i in range(max_row + 1)]
	count = 0
	for i in range(max_row + 1):
		for j in range(max_col + 1):
			if not visited[i][j] and grid[i][j] == 1:
				count = count + 1
				dfs_util(i, j, max_row, max_col, visited, grid)
	return count

def dfs_util(row: int, col: int, max_row: int, max_col: int, visited: [], grid: [[]]):
	if visited[row][col]:
		return
	visited[row][col] = True
	move_x = [1, -1, 0, 0, 1, 1, -1, -1]
	move_y = [0, 0, 1, -1, 1, -1, 1, -1]
	for i in range(8):
		new_row = row + move_y[i]
		new_col = col + move_x[i]
		if is_safe(new_row, new_col, grid, max_row, max_col, visited):
			dfs_util(new_row, new_col, max_row, max_col, visited, grid)

def is_safe(row: int, col: int, grid: [[]], max_row: int, max_col: int, visited: [[]]):
	if row < 0 or row > max_row:
		return False
	if col < 0 or col > max_col:
		return False
	if visited[row][col]:
		return False
	if grid[row][col] == 0:
		return False
	return True

class Solution:

	def numIslands(self, grid):
		return find_number_of_island(grid)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def bfs(self, vis, grid, row, col):
		q = []
		q.append((row, col))
		vis[row][col] = 1
		while q:
			(r, c) = q.pop(0)
			for delrow in range(-1, 2):
				for delcol in range(-1, 2):
					newrow = r + delrow
					newcol = c + delcol
					if newrow >= 0 and newcol >= 0 and (newrow < len(grid)) and (newcol < len(grid[0])) and (vis[newrow][newcol] == 0) and (grid[newrow][newcol] == 1):
						vis[newrow][newcol] = 1
						q.append((newrow, newcol))

	def numIslands(self, grid):
		c = 0
		row = len(grid)
		col = len(grid[0])
		vis = [[0 for j in range(col)] for i in range(row)]
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1 and vis[i][j] == 0:
					self.bfs(vis, grid, i, j)
					c += 1
		return c


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def trace(this, row, col):
		this.grid[row][col] = 0
		if row > 0:
			if col > 0:
				if this.grid[row - 1][col - 1] == 1:
					this.trace(row - 1, col - 1)
			if this.grid[row - 1][col] == 1:
				this.trace(row - 1, col)
			if col < this.m - 1:
				if this.grid[row - 1][col + 1] == 1:
					this.trace(row - 1, col + 1)
		if col > 0:
			if this.grid[row][col - 1] == 1:
				this.trace(row, col - 1)
		if col < this.m - 1:
			if this.grid[row][col + 1] == 1:
				this.trace(row, col + 1)
		if row < this.n - 1:
			if col > 0:
				if this.grid[row + 1][col - 1] == 1:
					this.trace(row + 1, col - 1)
			if this.grid[row + 1][col] == 1:
				this.trace(row + 1, col)
			if col < this.m - 1:
				if this.grid[row + 1][col + 1] == 1:
					this.trace(row + 1, col + 1)

	def numIslands(self, grid):
		self.grid = grid
		self.n = len(grid)
		self.m = len(grid[0])
		count = 0
		for i in range(self.n):
			for j in range(self.m):
				if self.grid[i][j] == 1:
					count += 1
					self.trace(i, j)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def bfs(i, j, vis):
			vis[i][j] = True
			q = []
			q.append([i, j])
			n = len(grid)
			m = len(grid[0])
			while len(q) > 0:
				(row, col) = q.pop(0)
				for delRow in range(-1, 2):
					for delCol in range(-1, 2):
						nRow = row + delRow
						nCol = col + delCol
						if nRow >= 0 and nRow < n and (nCol < m) and (nCol >= 0) and (grid[nRow][nCol] == 1) and (not vis[nRow][nCol]):
							vis[nRow][nCol] = True
							q.append([nRow, nCol])
		vis = [[False for i in range(len(grid[0]))] for i in range(len(grid))]
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 0 or vis[i][j]:
					continue
				count += 1
				bfs(i, j, vis)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		if not grid:
			return 0
		(rows, cols) = (len(grid), len(grid[0]))
		(visited, islands) = (set(), 0)

		def bfs(r, c):
			queue = []
			visited.add((r, c))
			queue.append((r, c))
			while queue:
				(row, col) = queue.pop(0)
				directions = [[1, 0], [-1, 0], [0, 1], [0, -1], [-1, 1], [1, -1], [-1, -1], [1, 1], [0, 0]]
				for (dr, dc) in directions:
					(r, c) = (row + dr, col + dc)
					if r in range(rows) and c in range(cols) and (grid[r][c] == 1) and ((r, c) not in visited):
						queue.append((r, c))
						visited.add((r, c))
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] == 1 and (r, c) not in visited:
					bfs(r, c)
					islands += 1
		return islands


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def bfs(self, row, col, vis, grid):
		vis[row][col] = 1
		queue = []
		n = len(grid)
		m = len(grid[0])
		queue.append((row, col))
		while len(queue) > 0:
			e = queue.pop(0)
			r = e[0]
			c = e[1]
			for i in range(-1, 2):
				for j in range(-1, 2):
					nrow = r + i
					ncol = c + j
					if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
						vis[nrow][ncol] = 1
						queue.append((nrow, ncol))

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for j in range(m)] for i in range(n)]
		count = 0
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and grid[i][j] == 1:
					count += 1
					self.bfs(i, j, vis, grid)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					ans = ans + 1
					self.dfs(len(grid), len(grid[0]), i, j, grid)
		return ans

	def dfs(self, m, n, i, j, A):
		if i < 0 or j < 0 or i >= m or (j >= n) or (A[i][j] == 0):
			return
		A[i][j] = 0
		self.dfs(m, n, i - 1, j, A)
		self.dfs(m, n, i, j - 1, A)
		self.dfs(m, n, i + 1, j, A)
		self.dfs(m, n, i, j + 1, A)
		self.dfs(m, n, i - 1, j - 1, A)
		self.dfs(m, n, i - 1, j + 1, A)
		self.dfs(m, n, i + 1, j - 1, A)
		self.dfs(m, n, i + 1, j + 1, A)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		vis = [[0 for j in range(len(grid[0]))] for i in range(len(grid))]
		c = 0
		(n, m) = (len(grid), len(grid[0]))
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (not vis[i][j]):
					c += 1
					self.bfs(i, j, grid, n, m, vis)
		return c

	def bfs(self, i, j, grid, n, m, vis):
		q = deque()
		q.append([i, j])
		vis[i][j] = 1
		while q:
			ns = q.popleft()
			(r, c) = (ns[0], ns[1])
			drow = [-1, -1, 0, 1, 1, 1, 0, -1]
			dcol = [0, 1, 1, 1, 0, -1, -1, -1]
			for i in range(8):
				(nrow, ncol) = (r + drow[i], c + dcol[i])
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (grid[nrow][ncol] == 1) and (not vis[nrow][ncol]):
					q.append([nrow, ncol])
					vis[nrow][ncol] = 1


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		r = len(grid)
		c = len(grid[0])
		cnt = 0
		visited = [[0] * c for i in range(r)]
		for i in range(r):
			for j in range(c):
				if not visited[i][j] and grid[i][j] == 1:
					self.dfs(visited, grid, i, j)
					cnt += 1
		return cnt

	def dfs(self, visited, grid, row, col):
		visited[row][col] = 1
		for i in range(-1, 2):
			for j in range(-1, 2):
				nrow = row + i
				ncol = col + j
				if nrow >= 0 and nrow < len(grid) and (ncol >= 0) and (ncol < len(grid[0])) and (not visited[nrow][ncol]) and (grid[nrow][ncol] == 1):
					self.dfs(visited, grid, nrow, ncol)


import sys
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		cnt = 0
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if visited[i][j] == False and grid[i][j] == 1:
					self.dfs(grid, visited, i, j)
					cnt += 1
		return cnt

	def dfs(self, grid, visited, row, col):
		n = len(grid)
		m = len(grid[0])
		visited[row][col] = 1
		for drow in range(-1, 2):
			for dcol in range(-1, 2):
				nrow = row + drow
				ncol = col + dcol
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (not visited[nrow][ncol]) and (grid[nrow][ncol] == 1):
					self.dfs(grid, visited, nrow, ncol)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, i, j, visited, grid):
		visited[i][j] = 1
		if i - 1 >= 0 and visited[i - 1][j] == 0 and (grid[i - 1][j] == 1):
			visited[i - 1][j] = 1
			self.dfs(i - 1, j, visited, grid)
		if i + 1 < len(grid) and visited[i + 1][j] == 0 and (grid[i + 1][j] == 1):
			visited[i + 1][j] = 1
			self.dfs(i + 1, j, visited, grid)
		if j - 1 >= 0 and visited[i][j - 1] == 0 and (grid[i][j - 1] == 1):
			visited[i][j - 1] = 1
			self.dfs(i, j - 1, visited, grid)
		if j + 1 < len(grid[0]) and visited[i][j + 1] == 0 and (grid[i][j + 1] == 1):
			visited[i][j + 1] = 1
			self.dfs(i, j + 1, visited, grid)
		if i - 1 >= 0 and j - 1 >= 0 and (visited[i - 1][j - 1] == 0) and (grid[i - 1][j - 1] == 1):
			visited[i - 1][j - 1] = 1
			self.dfs(i - 1, j - 1, visited, grid)
		if i - 1 >= 0 and j + 1 < len(grid[0]) and (visited[i - 1][j + 1] == 0) and (grid[i - 1][j + 1] == 1):
			visited[i - 1][j + 1] = 1
			self.dfs(i - 1, j + 1, visited, grid)
		if i + 1 < len(grid) and j - 1 >= 0 and (visited[i + 1][j - 1] == 0) and (grid[i + 1][j - 1] == 1):
			visited[i + 1][j - 1] = 1
			self.dfs(i + 1, j - 1, visited, grid)
		if i + 1 < len(grid) and j + 1 < len(grid[0]) and (visited[i + 1][j + 1] == 0) and (grid[i + 1][j + 1] == 1):
			visited[i + 1][j + 1] = 1
			self.dfs(i + 1, j + 1, visited, grid)

	def numIslands(self, grid):
		visited = []
		for i in range(len(grid)):
			arr = []
			for j in range(len(grid[0])):
				arr.append(0)
			visited.append(arr)
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visited[i][j] == 0 and grid[i][j] == 1:
					self.dfs(i, j, visited, grid)
					count += 1
		return count


import sys
sys.setrecursionlimit(10 ** 8)
dirx = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
diry = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
a = {(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)}

class Solution:

	def valid(self, x, y, vis, grid):
		if x < 0 or y < 0 or x > len(grid) - 1 or (y > len(grid[0]) - 1) or (vis[x][y] == True) or (grid[x][y] == 0):
			return False
		return True

	def numIslands(self, grid):
		vis = [[False for j in range(len(grid[0]))] for i in range(len(grid))]
		n = len(grid)
		m = len(grid[0])
		c = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == False:
					c = c + 1
					self.dfsUtil(vis, i, j, grid, n, m)
		return c

	def dfsUtil(self, vis, x, y, grid, n, m):
		vis[x][y] = True
		for i in dirx:
			for j in diry:
				if i == 0 and j == 0:
					continue
				new_x = x + i
				new_y = y + j
				if self.valid(new_x, new_y, vis, grid):
					self.dfsUtil(vis, new_x, new_y, grid, n, m)


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		rown = len(grid)
		coln = len(grid[0])
		visited = [[0 for i in range(coln)] for j in range(rown)]

		def bfs(row, col, visited, grid):
			visited[row][col] = 1
			queue = []
			queue.append([row, col])
			while queue:
				rowq = queue[0][0]
				colq = queue[0][1]
				queue.pop(0)
				for drow in range(-1, 2, 1):
					for dcol in range(-1, 2, 1):
						nrow = rowq + drow
						ncol = colq + dcol
						if ncol < coln and nrow < rown and (ncol > -1) and (nrow > -1) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
							visited[nrow][ncol] = 1
							queue.append([nrow, ncol])
		count = 0
		for r in range(rown):
			for c in range(coln):
				if visited[r][c] == 0 and grid[r][c] == 1:
					bfs(r, c, visited, grid)
					count = count + 1
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, adj):
		x = len(adj[0])
		y = len(adj)
		visited = [[0] * x for i in range(y)]
		count = 0
		for i in range(y):
			for j in range(x):
				if visited[i][j] == 0 and adj[i][j]:
					visited[i][j] = 1
					q = [[i, j]]
					ptr = 0
					while ptr < len(q):
						for a in range(-1, 2):
							for b in range(-1, 2):
								node = q[ptr]
								try:
									if node[0] - a >= 0 and node[1] - b >= 0 and adj[node[0] - a][node[1] - b] and (visited[node[0] - a][node[1] - b] == 0):
										visited[node[0] - a][node[1] - b] = 1
										q.append([node[0] - a, node[1] - b])
								except:
									pass
						ptr += 1
					count += 1
		return count


class Solution:

	def numIslands(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visited = set()
		stack = []
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (i, j) not in visited:
					count += 1
					stack.append((i, j))
					visited.add((i, j))
					while stack:
						(x, y) = stack.pop()
						for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]:
							(nx, ny) = (x + dx, y + dy)
							if 0 <= nx < n and 0 <= ny < m and (grid[nx][ny] == 1) and ((nx, ny) not in visited):
								stack.append((nx, ny))
								visited.add((nx, ny))
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfsTraverse(self, grid, row, col, gridRows, gridCols):
		traverseRange = [-1, 0, 1]
		for i in traverseRange:
			if row == 0 and i == -1 or (row == gridRows - 1 and i == 1):
				continue
			for j in traverseRange:
				if i == 0 and j == 0 or (col == 0 and j == -1) or (col == gridCols - 1 and j == 1):
					continue
				value = grid[row + i][col + j]
				if value != 1:
					continue
				grid[row + i][col + j] = 2
				self.dfsTraverse(grid, row + i, col + j, gridRows, gridCols)

	def numIslands(self, grid):
		noOfIslands = 0
		gridRows = len(grid)
		gridCols = len(grid[0])
		for row in range(gridRows):
			for col in range(gridCols):
				value = grid[row][col]
				if value == 1:
					noOfIslands += 1
					grid[row][col] = 2
					self.dfsTraverse(grid, row, col, gridRows, gridCols)
		return noOfIslands


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def __init__(self):
		self.seen = set()

	def next_unexplored_land(self, grid):
		for n in range(len(grid)):
			for m in range(len(grid[0])):
				if (n, m) not in self.seen and grid[n][m] == 1:
					self.seen.add((n, m))
					return (n, m)
		return None

	def is_island(self, grid, n, m):
		self.seen.add((n, m))
		p1 = (n - 1, m - 1)
		p2 = (n - 1, m)
		p3 = (n - 1, m + 1)
		p4 = (n, m - 1)
		p5 = (n, m + 1)
		p6 = (n + 1, m - 1)
		p7 = (n + 1, m)
		p8 = (n + 1, m + 1)
		n_minus_1_ok = n > 0
		n_plus_1_ok = n < len(grid) - 1
		m_minus_1_ok = m > 0
		m_plus_1_ok = m < len(grid[0]) - 1
		to_check = []
		if n_minus_1_ok:
			to_check.append(p2)
			if m_minus_1_ok:
				to_check.append(p1)
			if m_plus_1_ok:
				to_check.append(p3)
		if m_minus_1_ok:
			to_check.append(p4)
		if m_plus_1_ok:
			to_check.append(p5)
		if n_plus_1_ok:
			to_check.append(p7)
			if m_minus_1_ok:
				to_check.append(p6)
			if m_plus_1_ok:
				to_check.append(p8)
		return all([grid[p[0]][p[1]] == 0 or (p[0], p[1]) in self.seen or self.is_island(grid, p[0], p[1]) for p in to_check])

	def numIslands(self, grid):
		next_land = self.next_unexplored_land(grid)
		n_islands = 0
		while next_land is not None:
			(n, m) = next_land
			if self.is_island(grid, n, m):
				n_islands += 1
			next_land = self.next_unexplored_land(grid)
		return n_islands


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def getUnvisitedLandNeighbors(self, grid, visited, x, y):
		neighbors = []
		(M, N) = (len(grid), len(grid[0]))
		for (xoff, yoff) in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
			(x2, y2) = (x + xoff, y + yoff)
			if x2 < 0 or y2 < 0 or x2 >= M or (y2 >= N):
				continue
			if not visited[x2][y2] and grid[x2][y2] == 1:
				neighbors.append((x2, y2))
		return neighbors

	def bfsHelper(self, grid, visited, m, n):
		q = [(m, n)]
		while len(q) > 0:
			(i, j) = q.pop(0)
			visited[i][j] = True
			neighbors = self.getUnvisitedLandNeighbors(grid, visited, i, j)
			for (i2, j2) in neighbors:
				if not visited[i2][j2]:
					q.append((i2, j2))

	def dfsHelper(self, grid, visited, m, n):
		visited[m][n] = True
		neighbors = self.getUnvisitedLandNeighbors(grid, visited, m, n)
		for (i2, j2) in neighbors:
			if not visited[i2][j2]:
				self.dfsHelper(grid, visited, i2, j2)

	def numIslands(self, grid):
		(M, N) = (len(grid), len(grid[0]))
		visited = []
		for i in range(M):
			visited.append([False] * N)
		num_islands = 0
		for i in range(M):
			for j in range(N):
				if not visited[i][j] and grid[i][j] == 1:
					self.dfsHelper(grid, visited, i, j)
					num_islands += 1
		return num_islands


import sys
from queue import Queue
sys.setrecursionlimit(10 ** 8)

class Solution:

	def DFS(self, grid, i, j, visited):
		if i >= n or j >= m or i < 0 or (j < 0):
			return
		if grid[i][j] == 0:
			return
		if visited[i][j] == False:
			visited[i][j] = True
			rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]
			colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
			for k in range(8):
				self.DFS(grid, i + rowNbr[k], j + colNbr[k], visited)

	def numIslands(self, grid):
		visited = [[False for i in range(len(grid[0]))] for j in range(len(grid))]
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visited[i][j] == False and grid[i][j] == 1:
					self.DFS(grid, i, j, visited)
					count += 1
		return count


import sys
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		INF = -1
		rows = len(grid)
		cols = len(grid[0])
		islands = 0

		def isValid(ii, jj):
			return ii >= 0 and ii < rows and (jj >= 0) and (jj < cols)

		def bfs(i, j):
			queue = deque()
			queue.append((i, j))
			while queue:
				(i, j) = queue.popleft()
				if grid[i][j] == -1 or grid[i][j] == 0:
					continue
				grid[i][j] = -1
				for (r, c) in [[-1 + i, j], [1 + i, j], [i, -1 + j], [i, 1 + j], [i - 1, j - 1], [i + 1, j + 1], [i + 1, j - 1], [i - 1, j + 1]]:
					if isValid(r, c) and grid[r][c] == 1:
						queue.append((r, c))
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 1:
					bfs(i, j)
					islands += 1
		return islands


import sys
sys.setrecursionlimit(10 ** 8)
from collections import deque

class Solution:

	def numIslands(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		visited = [[0] * m for _ in range(n)]

		def dfs(row, col):
			q = deque()
			q.append([row, col])
			visited[row][col] = 1
			while q:
				(row, col) = q[0]
				q.popleft()
				for i in range(-1, 2):
					for j in range(-1, 2):
						nRow = row + i
						nCol = col + j
						if nRow >= 0 and nRow < n and (nCol >= 0) and (nCol < m) and (grid[nRow][nCol] == 1) and (not visited[nRow][nCol]):
							visited[nRow][nCol] = 1
							q.append([nRow, nCol])
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not visited[i][j]):
					count += 1
					dfs(i, j)
		return count


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def bfs(row, col, visited, grid):
			q = deque()
			visited[row][col] = True
			q.append([row, col])
			while q:
				f = q[0][0]
				s = q[0][1]
				q.popleft()
				for delrow in range(-1, 2):
					for delcol in range(-1, 2):
						nrow = f + delrow
						ncol = s + delcol
						if nrow >= 0 and nrow <= n - 1 and (ncol >= 0) and (ncol <= m - 1) and (grid[nrow][ncol] == 1) and (visited[nrow][ncol] == False):
							visited[nrow][ncol] = True
							q.append([nrow, ncol])
		n = len(grid)
		m = len(grid[0])
		count = 0
		visited = [[False for col in range(m)] for row in range(n)]
		for row in range(n):
			for col in range(m):
				if visited[row][col] == False and grid[row][col] == 1:
					count += 1
					bfs(row, col, visited, grid)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, G):

		def exists(G, i, j, n, m):
			return 0 <= i < n and 0 <= j < m and (G[i][j] == 1)

		def Visit(G, i, j):
			visited[i][j] = True
			if exists(G, i - 1, j - 1, n, m) and (not visited[i - 1][j - 1]):
				Visit(G, i - 1, j - 1)
			if exists(G, i - 1, j, n, m) and (not visited[i - 1][j]):
				Visit(G, i - 1, j)
			if exists(G, i - 1, j + 1, n, m) and (not visited[i - 1][j + 1]):
				Visit(G, i - 1, j + 1)
			if exists(G, i, j - 1, n, m) and (not visited[i][j - 1]):
				Visit(G, i, j - 1)
			if exists(G, i, j + 1, n, m) and (not visited[i][j + 1]):
				Visit(G, i, j + 1)
			if exists(G, i + 1, j - 1, n, m) and (not visited[i + 1][j - 1]):
				Visit(G, i + 1, j - 1)
			if exists(G, i + 1, j, n, m) and (not visited[i + 1][j]):
				Visit(G, i + 1, j)
			if exists(G, i + 1, j + 1, n, m) and (not visited[i + 1][j + 1]):
				Visit(G, i + 1, j + 1)
		n = len(G)
		m = len(G[0])
		visited = [[False for _ in range(m)] for _ in range(n)]
		island_count = 0
		for i in range(n):
			for j in range(m):
				if G[i][j] == 1 and (not visited[i][j]):
					island_count += 1
					Visit(G, i, j)
		return island_count


import sys
from queue import Queue
sys.setrecursionlimit(10 ** 8)

class Solution:

	@staticmethod
	def __bfs__(grid: list, visited: list, grid_row: int, grid_col: int):
		n = len(grid)
		m = len(grid[grid_row])
		q = Queue()
		visited[grid_row][grid_col] = True
		q.put((grid_row, grid_col))
		while not q.empty():
			(row, col) = q.get()
			adjacent_nodes = [(row, col - 1), (row, col + 1), (row - 1, col), (row + 1, col), (row + 1, col - 1), (row + 1, col + 1), (row - 1, col - 1), (row - 1, col + 1)]
			for traversal in adjacent_nodes:
				(temp_row, temp_col) = traversal
				if n > temp_row >= 0 and 0 <= temp_col < m and (not visited[temp_row][temp_col]) and (grid[temp_row][temp_col] != 0):
					q.put(traversal)
					visited[temp_row][temp_col] = True

	def numIslands(self, grid: list) -> int:
		(size_n, size_m) = (len(grid), len(grid[0]))
		if not grid or size_n == 0:
			return 0
		visited = [[False for _ in range(size_m)] for _ in grid]
		count = 0
		for row in range(size_n):
			for col in range(size_m):
				if not visited[row][col] and grid[row][col] != 0:
					self.__bfs__(grid, visited, row, col)
					count = count + 1
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[False for _ in range(m)] for _ in range(n)]
		counter = 0

		def DFSVisit(grid, i, j):
			nonlocal visited
			visited[i][j] = True
			for (v, w) in [(0, 1), (1, 0), (0, -1), (-1, 0), (-1, -1), (1, 1), (-1, 1), (1, -1)]:
				if 0 <= i + v < n and 0 <= j + w < m:
					if not visited[i + v][j + w] and grid[i + v][j + w] == 1:
						DFSVisit(grid, i + v, j + w)
		for i in range(n):
			for j in range(m):
				if not visited[i][j] and grid[i][j] == 1:
					counter += 1
					DFSVisit(grid, i, j)
		return counter


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		moves = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [-1, 1], [1, -1], [-1, -1]]
		visited = [[0 for _ in range(m)] for __ in range(n)]
		count = 0

		def isValid(i, j):
			if i < 0 or j < 0 or i >= n or (j >= m) or (grid[i][j] == 0):
				return False
			return True

		def dfs(i, j):
			if not isValid(i, j):
				return
			if visited[i][j]:
				return
			visited[i][j] = 1
			for move in moves:
				dfs(i + move[0], j + move[1])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not visited[i][j]):
					count += 1
				dfs(i, j)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		ans = 0
		rows = len(grid)
		cols = len(grid[0])
		vis = [[0 for i in range(cols)] for j in range(rows)]
		ans = 0

		def dfs(r, c):
			vis[r][c] = 1
			for i in range(-1, 2):
				for j in range(-1, 2):
					x = r + i
					y = c + j
					if x >= 0 and x < rows and (y >= 0) and (y < cols) and (grid[x][y] == 1) and (vis[x][y] == 0):
						dfs(x, y)
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 1 and vis[i][j] == 0:
					ans += 1
					dfs(i, j)
		return ans


import sys
sys.setrecursionlimit(10 ** 8)
from collections import deque

def bfs(i, j, grid, vis):
	n = len(grid)
	m = len(grid[0])
	queue = deque()
	vis[i][j] = 1
	queue.append([i, j])
	while len(queue) != 0:
		row = queue.popleft()[0]
		col = queue.popleft()[1]
		for drow in range(-1, 2):
			for dcol in range(-1, 2):
				nrow = drow + i
				ncol = dcol + j
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m):
					if grid[nrow][ncol] == 1 and vis[nrow][ncol] != 1:
						queue.append([nrow][ncol])
						vis[nrow][ncol] = 1

def dfs(row, col, grid, vis):
	n = len(grid)
	m = len(grid[0])
	vis[row][col] = 1
	for drow in range(-1, 2):
		for dcol in range(-1, 2):
			nrow = drow + row
			ncol = dcol + col
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (grid[nrow][ncol] == 1) and (vis[nrow][ncol] != 1):
				dfs(nrow, ncol, grid, vis)

class Solution:

	def numIslands(self, grid):
		vis = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if vis[i][j] != 1 and grid[i][j] == 1:
					dfs(i, j, grid, vis)
					count += 1
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def DFS(self, grid, visited, row, col):
		visited[row][col] = 1
		(n, m) = (len(grid), len(grid[0]))
		dirs = [[-1, 0], [1, 0], [0, 1], [0, -1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
		for (b, c) in dirs:
			ROW = row + b
			COL = col + c
			if 0 <= ROW and ROW < n and (COL < m) and (COL >= 0):
				if visited[ROW][COL] == 1:
					continue
				elif grid[ROW][COL] == 1:
					self.DFS(grid, visited, ROW, COL)

	def numIslands(self, grid):
		visited = []
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			visited.append([0] * m)
		count = 0
		for row in range(n):
			for col in range(m):
				if grid[row][col]:
					if visited[row][col] == 1:
						continue
					else:
						self.DFS(grid, visited, row, col)
						count = count + 1
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		count = 0
		v = [[0 for j in range(m)] for i in range(n)]

		def bfs(k, l, grid, v, n, m):
			v[k][l] = 1
			dr = [-1, 1, 0, 1, 1, -1, 0, -1]
			dc = [0, 1, 1, -1, 0, -1, -1, 1]
			for i in range(len(dr)):
				nr = k + dr[i]
				nc = l + dc[i]
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (not v[nr][nc]) and grid[nr][nc]:
					bfs(nr, nc, grid, v, n, m)
		for i in range(n):
			for j in range(m):
				if v[i][j] != 1 and grid[i][j] == 1:
					count = count + 1
					bfs(i, j, grid, v, n, m)
		return count


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def bfs(self, row, col, visited, grid):
		visited[row][col] = True
		n = len(grid)
		m = len(grid[0])
		queue = deque()
		queue.append((row, col))
		while queue:
			(row, col) = queue.popleft()
			directions = [[-1, 0], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, -1]]
			for direction in directions:
				new_r = row + direction[0]
				new_c = col + direction[1]
				if new_r >= 0 and new_r < n and (new_c >= 0) and (new_c < m) and (not visited[new_r][new_c]) and (grid[new_r][new_c] == 1):
					visited[new_r][new_c] = True
					queue.append((new_r, new_c))

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = []
		for i in range(n):
			c = []
			for j in range(m):
				c.append(False)
			visited.append(c)
		cnt = 0
		for row in range(n):
			for col in range(m):
				if not visited[row][col] and grid[row][col] == 1:
					cnt += 1
					self.bfs(row, col, visited, grid)
		return cnt


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def dfs(i, j, grid, vis):
			if i >= n or j >= m or i < 0 or (j < 0):
				return
			if grid[i][j] == 0:
				return
			if vis[i][j] == 0:
				vis[i][j] = 1
				dfs(i + 1, j, grid, vis)
				dfs(i - 1, j, grid, vis)
				dfs(i, j + 1, grid, vis)
				dfs(i, j - 1, grid, vis)
				dfs(i + 1, j + 1, grid, vis)
				dfs(i + 1, j - 1, grid, vis)
				dfs(i - 1, j + 1, grid, vis)
				dfs(i - 1, j - 1, grid, vis)
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for _ in range(m)] for _ in range(n)]
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and visited[i][j] == 0:
					dfs(i, j, grid, visited)
					count += 1
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isSafe(self, n, m, x, y):
		return x >= 0 and x < n and (y >= 0) and (y < m)

	def dfs(self, grid, n, m, i, j, visited):
		x_d = [-1, -1, -1, 0, 0, 1, 1, 1]
		y_d = [-1, 0, 1, -1, 1, -1, 0, 1]
		for u in range(0, 8):
			x = i + x_d[u]
			y = j + y_d[u]
			if self.isSafe(n, m, x, y) and (not visited[x][y]) and grid[x][y]:
				visited[x][y] = 1
				self.dfs(grid, n, m, x, y, visited)

	def numIslands(self, grid):
		island_count = 0
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] and (not visited[i][j]):
					island_count += 1
					self.dfs(grid, n, m, i, j, visited)
		return island_count


import sys
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):

		def bfs(x, y):
			vis[x][y] = 1
			q = deque([[x, y]])
			poss = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [-1, 1], [1, -1], [-1, -1]]
			while q:
				(xc, yc) = q.popleft()
				for (xi, yi) in poss:
					nx = xc + xi
					ny = yc + yi
					if 0 <= nx < n and 0 <= ny < m:
						if grid[nx][ny]:
							if not vis[nx][ny]:
								vis[nx][ny] = 1
								q.append([nx, ny])
		(n, m) = (len(grid), len(grid[0]))
		vis = [[0] * m for i in range(n)]
		c = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] and (not vis[i][j]):
					bfs(i, j)
					c += 1
		return c


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, mat, i, j, vis):
		if i >= n or j >= m or i < 0 or (j < 0):
			return
		if mat[i][j] == 0:
			return
		if vis[i][j] == 0:
			vis[i][j] = 1
			self.dfs(mat, i + 1, j, vis)
			self.dfs(mat, i - 1, j, vis)
			self.dfs(mat, i, j + 1, vis)
			self.dfs(mat, i, j - 1, vis)
			self.dfs(mat, i + 1, j + 1, vis)
			self.dfs(mat, i + 1, j - 1, vis)
			self.dfs(mat, i - 1, j + 1, vis)
			self.dfs(mat, i - 1, j - 1, vis)

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for i in range(501)] for j in range(501)]
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and visited[i][j] == 0:
					self.dfs(grid, i, j, visited)
					count += 1
		return count


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		visit = [[0] * m for _ in range(n)]

		def bfs(r, c):
			q = deque()
			q.append((r, c))
			while q:
				(r1, c1) = q.popleft()
				visit[r1][c1] = 1
				l = [[-1, 0], [1, 0], [0, 1], [0, -1], [-1, -1], [-1, 1], [1, 1], [1, -1]]
				for (i, j) in l:
					(nr, nc) = (r1 + i, c1 + j)
					if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (grid[nr][nc] == 1) and (not visit[nr][nc]):
						visit[nr][nc] = 1
						q.append((nr, nc))
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not visit[i][j]):
					count += 1
					bfs(i, j)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		count = 0
		visited = {}

		def function(grid, i, j, visited):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] != 1):
				return
			grid[i][j] = -1
			function(grid, i + 1, j, visited)
			function(grid, i - 1, j, visited)
			function(grid, i, j + 1, visited)
			function(grid, i, j - 1, visited)
			function(grid, i + 1, j + 1, visited)
			function(grid, i - 1, j - 1, visited)
			function(grid, i + 1, j - 1, visited)
			function(grid, i - 1, j + 1, visited)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and (i, j) not in visited:
					visited[i, j] = 'T'
					count = count + 1
					function(grid, i, j, visited)
		return count


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def bfs(self, vis, grid, si, sj):
		vis[si][sj] = 1
		n = len(grid)
		m = len(grid[0])
		q = [(si, sj)]
		while len(q) != 0:
			node = q.pop()
			orow = node[0]
			ocol = node[1]
			for i in range(-1, 2):
				for j in range(-1, 2):
					nrow = orow + i
					ncol = ocol + j
					if 0 <= nrow < n and 0 <= ncol < m and (not vis[nrow][ncol]) and grid[nrow][ncol]:
						vis[nrow][ncol] = 1
						q.append((nrow, ncol))

	def dfs(self, vis, grid, si, sj):
		vis[si][sj] = 1
		for i in range(-1, 2):
			for j in range(-1, 2):
				nrow = si + i
				ncol = sj + j
				if 0 <= nrow < n and 0 <= ncol < m and (not vis[nrow][ncol]) and grid[nrow][ncol]:
					self.dfs(vis, grid, nrow, ncol)

	def numIslands(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for _ in range(m)] for i in range(n)]
		c = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not vis[i][j]):
					c += 1
					self.dfs(vis, grid, i, j)
		return c


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def numIslands(self, grid):
		row = len(grid)
		col = len(grid[0])

		def dfs(x, y):
			grid[x][y] = 0
			if x - 1 >= 0 and x - 1 < row and (y >= 0) and (y < col) and (grid[x - 1][y] == 1):
				dfs(x - 1, y)
			if x + 1 >= 0 and x + 1 < row and (y >= 0) and (y < col) and (grid[x + 1][y] == 1):
				dfs(x + 1, y)
			if x >= 0 and x < row and (y - 1 >= 0) and (y - 1 < col) and (grid[x][y - 1] == 1):
				dfs(x, y - 1)
			if x >= 0 and x < row and (y + 1 >= 0) and (y + 1 < col) and (grid[x][y + 1] == 1):
				dfs(x, y + 1)
			if x - 1 >= 0 and x - 1 < row and (y - 1 >= 0) and (y - 1 < col) and (grid[x - 1][y - 1] == 1):
				dfs(x - 1, y - 1)
			if x - 1 >= 0 and x - 1 < row and (y + 1 >= 0) and (y + 1 < col) and (grid[x - 1][y + 1] == 1):
				dfs(x - 1, y + 1)
			if x + 1 >= 0 and x + 1 < row and (y - 1 >= 0) and (y - 1 < col) and (grid[x + 1][y - 1] == 1):
				dfs(x + 1, y - 1)
			if x + 1 >= 0 and x + 1 < row and (y + 1 >= 0) and (y + 1 < col) and (grid[x + 1][y + 1] == 1):
				dfs(x + 1, y + 1)
		ans = 0
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1:
					ans += 1
					dfs(i, j)
		return ans