Given  a grid of n*m consisting of O's and X's. The task is to find the number of 'X' total shapes.
Note: 'X' shape consists of one or more adjacent X's (diagonals not included).
 
Example 1:
Input: grid = {{X,O,X},{O,X,O},{X,X,X}}
Output: 3
Explanation: 
The grid is-
X O X
O X O
X X X
So, X with same colour are adjacent to each 
other vertically for horizontally (diagonals 
not included). So, there are 3 different groups 
in the given grid.
Example 2:
Input: grid = {{X,X},{X,X}}
Output: 1
Expanation: 
The grid is- 
X X
X X
So, X with same colour are adjacent to each
other vertically for horizontally (diagonals
not included). So, there is only 1 group
in the given grid.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function xShape() which takes grid as input parameter and returns the count of total X shapes.
 
Expected Time Compelxity: O(n*m)
Expected Space Compelxity: O(n*m)
 
Constraints:
1 ≤ n, m ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: 

class Solution:
    
    #Function to find the number of 'X' total shapes.
	def xShape(self, grid):
		#Code here

Solutions:
class Solution:

	def solver(self, x, y):
		if x < 0 or x >= self.row or y < 0 or (y >= self.col) or (grid[x][y] == 'O'):
			return 0
		grid[x][y] = 'O'
		for (x1, y1) in [[-1, 0], [0, -1], [0, 1], [1, 0]]:
			self.solver(x + x1, y + y1)

	def xShape(self, grid):
		(self.row, self.col, area) = (len(grid), len(grid[0]), 0)
		for i in range(self.row):
			for j in range(self.col):
				if grid[i][j] == 'X':
					self.solver(i, j)
					area += 1
		return area


class Solution:

	def xShape(self, grid):

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

		def visitAdjacents(grid, n, m, x, y):
			if validboundaries(n, m + 1, x, y):
				if grid[n][m + 1] == 'X':
					grid[n][m + 1] = 'Z'
					visitAdjacents(grid, n, m + 1, x, y)
			if validboundaries(n + 1, m, x, y):
				if grid[n + 1][m] == 'X':
					grid[n + 1][m] = 'Z'
					visitAdjacents(grid, n + 1, m, x, y)
			if validboundaries(n - 1, m, x, y):
				if grid[n - 1][m] == 'X':
					grid[n - 1][m] = 'Z'
					visitAdjacents(grid, n - 1, m, x, y)
			if validboundaries(n, m - 1, x, y):
				if grid[n][m - 1] == 'X':
					grid[n][m - 1] = 'Z'
					visitAdjacents(grid, n, m - 1, x, y)
			return
		x = len(grid)
		y = len(grid[0])
		count = 0
		for n in range(x):
			for m in range(y):
				if grid[n][m] == 'X':
					grid[n][m] == 'Z'
					visitAdjacents(grid, n, m, x, y)
					count += 1
		return count


class Solution:

	def xShape(self, grid):
		(rows, cols) = (len(grid), 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] != 'X'):
				return
			visit.add((r, c))
			dfs(r + 1, c)
			dfs(r - 1, c)
			dfs(r, c - 1)
			dfs(r, c + 1)
		for r in range(rows):
			for c in range(cols):
				if grid[r][c] == 'X' and (r, c) not in visit:
					dfs(r, c)
					res += 1
		return res


class Solution:

	def Visit(self, comp_id, grid, visited, n, m, r, c):
		visited[r][c] = comp_id
		for dr in (-1, 1):
			if r + dr < 0 or r + dr >= n:
				continue
			if grid[r + dr][c] == 'X' and (not visited[r + dr][c]):
				self.Visit(comp_id, grid, visited, n, m, r + dr, c)
		for dc in (-1, 1):
			if c + dc < 0 or c + dc >= m:
				continue
			if grid[r][c + dc] == 'X' and (not visited[r][c + dc]):
				self.Visit(comp_id, grid, visited, n, m, r, c + dc)

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		num_comps = 0
		visited = []
		for r in range(n):
			visited.append([False] * m)
		for r in range(n):
			for c in range(m):
				if grid[r][c] == 'X' and (not visited[r][c]):
					num_comps += 1
					self.Visit(num_comps, grid, visited, n, m, r, c)
		return num_comps


def dfs(r, c, visit, grid):
	(n, m) = (len(grid), len(grid[0]))
	visit[r][c] = 1
	l = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	for (i, j) in l:
		(nr, nc) = (r + i, c + j)
		if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (grid[nr][nc] == 'X') and (not visit[nr][nc]):
			dfs(nr, nc, visit, grid)

class Solution:

	def xShape(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		c = 0
		visit = [[0] * m for _ in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X' and (not visit[i][j]):
					c += 1
					dfs(i, j, visit, grid)
		return c


class Solution:

	def xShape(self, grid):

		def sol(G):

			def Visit(G, n, m, i, j):
				G[i][j] = 'O'
				if i > 0 and G[i - 1][j] == 'X':
					Visit(G, n, m, i - 1, j)
				if i < n - 1 and G[i + 1][j] == 'X':
					Visit(G, n, m, i + 1, j)
				if j > 0 and G[i][j - 1] == 'X':
					Visit(G, n, m, i, j - 1)
				if j < m - 1 and G[i][j + 1] == 'X':
					Visit(G, n, m, i, j + 1)
			n = len(G)
			m = len(G[0])
			counter = 0
			for i in range(n):
				for j in range(m):
					if G[i][j] == 'X':
						counter += 1
						Visit(G, n, m, i, j)
			return counter
		return sol(grid)


class Solution:

	def xShape(self, grid):

		def dfs(i, j, grid, visited):
			visited[i][j] = True
			dx = [-1, 0, 1, 0]
			dy = [0, 1, 0, -1]
			for u in range(4):
				nx = i + dx[u]
				ny = j + dy[u]
				if nx >= 0 and nx < len(grid) and (ny >= 0) and (ny < len(grid[0])) and (visited[nx][ny] == False) and (grid[nx][ny] == 'X'):
					visited[nx][ny] == True
					dfs(nx, ny, grid, visited)
		visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
		cnt = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visited[i][j] == False and grid[i][j] == 'X':
					dfs(i, j, grid, visited)
					cnt += 1
		return cnt


class Solution:

	def __init__(self):
		self.X = 'X'
		self.directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		self.visited = set()

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

	def dfs(self, i, j):
		self.visited.add((i, j))
		for (r, c) in self.directions:
			row = i + r
			column = j + c
			if 0 <= row < self.n and 0 <= column < self.m and ((row, column) not in self.visited) and (grid[i][j] == self.X):
				self.dfs(row, column)


from collections import deque

class Solution:

	@staticmethod
	def _bfs_helper(grid, i, j, visited):
		nodes_to_explore = deque()
		dx = [[-1, 0], [0, 1], [1, 0], [0, -1]]
		nodes_to_explore.append([i, j])
		while nodes_to_explore:
			(cur_i, cur_j) = nodes_to_explore.popleft()
			if visited[cur_i][cur_j]:
				continue
			visited[cur_i][cur_j] = True
			for (next_i_dx, next_j_dx) in dx:
				(next_i, next_j) = (cur_i + next_i_dx, cur_j + next_j_dx)
				if next_i >= 0 and next_i < len(grid) and (next_j >= 0) and (next_j < len(grid[0])):
					if not visited[next_i][next_j] and grid[next_i][next_j] == 'X':
						nodes_to_explore.append([next_i, next_j])

	def xShape(self, grid):
		visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'X' and (not visited[i][j]):
					ans += 1
					self._bfs_helper(grid, i, j, visited)
		return ans


from collections import deque

class Solution:

	def xShape(self, grid):
		m = len(grid)
		n = len(grid[0])
		visited = [[False for i in range(n)] for j in range(m)]
		q = deque()
		count = 0
		for i in range(m):
			for j in range(n):
				if visited[i][j] == False and grid[i][j] == 'X':
					q.append([i, j])
					count += 1
					while len(q) != 0:
						idx = q.popleft()
						x = idx[0]
						y = idx[1]
						grid[x][y] = 'O'
						visited[x][y] = True
						if x - 1 >= 0 and grid[x - 1][y] == 'X' and (visited[x - 1][y] == False):
							q.append([x - 1, y])
						if y - 1 >= 0 and grid[x][y - 1] == 'X' and (visited[x][y - 1] == False):
							q.append([x, y - 1])
						if x + 1 < m and grid[x + 1][y] == 'X' and (visited[x + 1][y] == False):
							q.append([x + 1, y])
						if y + 1 < n and grid[x][y + 1] == 'X' and (visited[x][y + 1] == False):
							q.append([x, y + 1])
		return count


class Solution:

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

		def dfs(i, j):
			visited[i][j] = 1
			for (delRow, delCol) in dirc:
				nr = delRow + i
				nc = delCol + j
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (grid[nr][nc] == 'X') and (not visited[nr][nc]):
					dfs(nr, nc)
		cnt = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X' and (not visited[i][j]):
					dfs(i, j)
					cnt += 1
		return cnt


class Solution:

	def xShape(self, grid):

		def dfs(i, j, n, m, grid):
			if i < 0 or j < 0 or i == n or (j == m) or (grid[i][j] == 'O'):
				return
			grid[i][j] = 'O'
			dfs(i + 1, j, n, m, grid)
			dfs(i - 1, j, n, m, grid)
			dfs(i, j + 1, n, m, grid)
			dfs(i, j - 1, n, m, grid)
		c = 0
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X':
					c += 1
					dfs(i, j, n, m, grid)
		return c


class Solution:

	def xShape(self, grid):
		n = len(grid)
		res = 0
		n = len(grid)
		m = len(grid[0])
		visited = [[False for i in range(m)] for j in range(n)]

		def dfs(r, c, par_r, par_c):
			nonlocal n
			nonlocal m
			if r == n or c == m or r < 0 or (c < 0):
				return
			if grid[r][c] == 'O':
				return
			if visited[r][c]:
				return
			visited[r][c] = True
			if not (r - 1 == par_r and c == par_c):
				dfs(r - 1, c, r, c)
			if not (r + 1 == par_r and c == par_c):
				dfs(r + 1, c, r, c)
			if not (r == par_r and c - 1 == par_c):
				dfs(r, c - 1, r, c)
			if not (r == par_r and c + 1 == par_c):
				dfs(r, c + 1, r, c)
		for r in range(n):
			for c in range(m):
				if grid[r][c] == 'X' and (not visited[r][c]):
					dfs(r, c, None, None)
					res += 1
		return res


class Solution:

	def dfs(self, i, j, g, vis):
		m = len(grid)
		n = len(grid[0])
		if i >= 0 and i < m and (j >= 0) and (j < n) and (g[i][j] == 'X') and (vis[i][j] == False):
			vis[i][j] = True
			self.dfs(i + 1, j, g, vis)
			self.dfs(i - 1, j, g, vis)
			self.dfs(i, j + 1, g, vis)
			self.dfs(i, j - 1, g, vis)

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


class Solution:

	def xShape(self, grid):
		ct = 0
		(r, c) = (len(grid), len(grid[0]))
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 'X':
					ct += 1
					s = [[i, j]]
					while len(s) != 0:
						(m, n) = s.pop(0)
						grid[m][n] = 'T'
						if m + 1 < r and n >= 0 and (grid[m + 1][n] == 'X'):
							s.append([m + 1, n])
						if m - 1 >= 0 and n >= 0 and (grid[m - 1][n] == 'X'):
							s.append([m - 1, n])
						if m < r and m >= 0 and (n + 1 < c) and (n + 1 >= 0) and (grid[m][n + 1] == 'X'):
							s.append([m, n + 1])
						if m < r and m >= 0 and (n - 1 < c) and (n - 1 >= 0) and (grid[m][n - 1] == 'X'):
							s.append([m, n - 1])
		return ct


class Solution:

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

	def dfsUtil(self, source, grid, visited):
		(m, n) = (len(grid), len(grid[0]))
		(si, sj) = source
		if grid[si][sj] == 'O':
			return
		visited[si][sj] = True
		if si - 1 >= 0 and (not visited[si - 1][sj]):
			self.dfsUtil((si - 1, sj), grid, visited)
		if si + 1 < m and (not visited[si + 1][sj]):
			self.dfsUtil((si + 1, sj), grid, visited)
		if sj - 1 >= 0 and (not visited[si][sj - 1]):
			self.dfsUtil((si, sj - 1), grid, visited)
		if sj + 1 < n and (not visited[si][sj + 1]):
			self.dfsUtil((si, sj + 1), grid, visited)


class Solution:

	def util(self, grid, visited, m, n, i, j):
		if i < 0 or j < 0 or i > m - 1 or (j > n - 1) or (grid[i][j] == 'O') or ((i, j) in visited):
			return
		visited.add((i, j))
		self.util(grid, visited, m, n, i + 1, j)
		self.util(grid, visited, m, n, i - 1, j)
		self.util(grid, visited, m, n, i, j + 1)
		self.util(grid, visited, m, n, i, j - 1)

	def xShape(self, grid):
		visited = set()
		cnt = 0
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'X' and (i, j) not in visited:
					self.util(grid, visited, m, n, i, j)
					cnt += 1
		return cnt


class Solution:

	def dfs(self, x, y, grid):
		rows = [0, 1, 0, -1]
		cols = [-1, 0, 1, 0]
		grid[x][y] = -1
		n = len(grid[0])
		m = len(grid)
		for k in range(4):
			if 0 <= x + cols[k] < m and 0 <= y + rows[k] < n and (grid[x + cols[k]][y + rows[k]] == 'X'):
				self.dfs(x + cols[k], y + rows[k], grid)

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


class Solution:

	def xShape(self, grid):
		di = [0, 1, 0, -1]
		dj = [1, 0, -1, 0]
		visited = set()

		def dfs(i, j):
			visited.add((i, j))
			for d in range(4):
				newi = di[d] + i
				newj = j + dj[d]
				if not (0 <= newi < len(grid) and 0 <= newj < len(grid[0])):
					continue
				if (newi, newj) in visited or grid[newi][newj] == 'O':
					continue
				dfs(newi, newj)
		cnt = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'X' and (i, j) not in visited:
					dfs(i, j)
					cnt += 1
		return cnt


class Solution:

	def xShape(self, grid):

		def func(row, col, n, m, grid):
			que = [[row, col]]
			grid[row][col] = '#'
			dicrow = [-1, 0, 1, 0]
			diccol = [0, 1, 0, -1]
			while que:
				(row1, col1) = que.pop(0)
				for i in range(4):
					nrow = row1 + dicrow[i]
					ncol = col1 + diccol[i]
					if nrow >= 0 and ncol >= 0 and (nrow < n) and (ncol < m) and (grid[nrow][ncol] == 'X'):
						grid[nrow][ncol] = '#'
						que.append([nrow, ncol])
		ans = 0
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X':
					ans += 1
					func(i, j, n, m, grid)
		return ans


class Solution:

	def dfs(self, row, col, visited, grid, n, m):
		if row >= 0 and row < n and (col < m) and (col >= 0) and (visited[row][col] == 0) and (grid[row][col] == 'X'):
			visited[row][col] = 1
			self.dfs(row - 1, col, visited, grid, n, m)
			self.dfs(row + 1, col, visited, grid, n, m)
			self.dfs(row, col - 1, visited, grid, n, m)
			self.dfs(row, col + 1, visited, grid, n, m)

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


class Solution:

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		level = 0
		count = 0
		while level < n:
			if 'X' in grid[level]:
				count += 1
				stack = [(level, grid[level].index('X'))]
				while stack:
					(i, j) = stack.pop()
					if grid[i][j] == 'O':
						continue
					grid[i][j] = 'O'
					if i > 0:
						stack.append((i - 1, j))
					if i < n - 1:
						stack.append((i + 1, j))
					if j > 0:
						stack.append((i, j - 1))
					if j < m - 1:
						stack.append((i, j + 1))
			else:
				level += 1
		return count


class Solution:

	def xShape(self, grid):
		visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if not visited[i][j] and grid[i][j] == 'X':
					count += 1
					self.dfs(grid, i, j, visited)
		return count

	def dfs(self, grid, i, j, visited):
		visited[i][j] = True
		for (dx, dy) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
			nr = i + dx
			nc = j + dy
			if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (grid[nr][nc] == 'X') and (not visited[nr][nc]):
				self.dfs(grid, nr, nc, visited)


from collections import deque

def bfs(grid, r, c, n, m):
	rl = [-1, 1, 0, 0]
	cl = [0, 0, -1, 1]
	grid[r][c] = 'O'
	q = deque()
	q.append([r, c])
	while len(q) > 0:
		temp = q.popleft()
		row = temp[0]
		col = temp[1]
		for i in range(4):
			newrow = row + rl[i]
			newcol = col + cl[i]
			if newrow >= 0 and newrow < n and (newcol >= 0) and (newcol < m):
				if grid[newrow][newcol] == 'X':
					grid[newrow][newcol] = 'O'
					q.append([newrow, newcol])

class Solution:

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		res = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X':
					res += 1
					bfs(grid, i, j, n, m)
		return res


class Solution:

	def xShape(self, grid):
		count = 0
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if grid[i][j] == 'X':
					self.traverse(grid, i, j)
					count += 1
		return count

	def traverse(self, grid, i, j):
		grid[i][j] = 'O'
		if i - 1 >= 0:
			if grid[i - 1][j] == 'X':
				self.traverse(grid, i - 1, j)
		if j - 1 >= 0:
			if grid[i][j - 1] == 'X':
				self.traverse(grid, i, j - 1)
		if i + 1 < len(grid):
			if grid[i + 1][j] == 'X':
				self.traverse(grid, i + 1, j)
		if j + 1 < len(grid[0]):
			if grid[i][j + 1] == 'X':
				self.traverse(grid, i, j + 1)
		return


class Solution:

	def xShape(self, grid):

		def bfs(grid, i, j):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])):
				return
			if grid[i][j] == 'X':
				grid[i][j] = '0'
				bfs(grid, i + 1, j)
				bfs(grid, i, j + 1)
				bfs(grid, i, j - 1)
				bfs(grid, i - 1, j)
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'X':
					bfs(grid, i, j)
					ans = ans + 1
		return ans


class Solution:

	def xShape(self, M):
		(R, C) = (len(M), len(M[0]))
		comps = 0
		for r in range(R):
			for c in range(C):
				if M[r][c] == 'X':
					comps += 1
					dfs(r, c, M, R, C)
		return comps

def dfs(r, c, M, R, C):
	if r < 0 or r == R or c < 0 or (c == C):
		return
	if M[r][c] != 'X':
		return
	M[r][c] = 'O'
	for (nr, nc) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
		dfs(nr, nc, M, R, C)


import sys

class Solution:

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

	def dfs(self, x, y, moves, grid, visited):
		visited[x][y] = True
		for move in moves:
			nx = x + move[0]
			ny = y + move[1]
			if not self.isValid(nx, ny, len(grid), len(grid[0])):
				continue
			if not visited[nx][ny] and grid[nx][ny] == 'X':
				self.dfs(nx, ny, moves, grid, visited)

	def xShape(self, grid):
		sys.setrecursionlimit(10 ** 6)
		n = len(grid)
		m = len(grid[0])
		moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		visited = [[False for _ in range(m)] for _ in range(n)]
		ans = 0
		for i in range(n):
			for j in range(m):
				if not visited[i][j] and grid[i][j] == 'X':
					self.dfs(i, j, moves, grid, visited)
					ans += 1
		return ans


arr = [[1, 0], [-1, 0], [0, 1], [0, -1]]

class Solution:

	def xShape(self, grid):
		m = len(grid)
		n = len(grid[0])
		count = 0
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'O':
					visited[i][j] = True
		for i in range(m):
			for j in range(n):
				if not visited[i][j]:
					count += 1
					self.helper(i, j, visited)
		return count

	def helper(self, i, j, visited):
		if i >= 0 and i < len(visited) and (j >= 0) and (j < len(visited[0])) and (not visited[i][j]):
			visited[i][j] = True
			for k in arr:
				self.helper(i + k[0], j + k[1], visited)


class Solution:

	def xShape(self, grid):
		rows = len(grid)
		cols = len(grid[-1])

		def fun(i, j):
			if i < 0 or j < 0 or j >= cols or (i >= rows):
				return 0
			elif grid[i][j] == 'O':
				return 0
			grid[i][j] = 'O'
			fun(i + 1, j)
			fun(i - 1, j)
			fun(i, j - 1)
			fun(i, j + 1)
		c = 0
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 'X':
					fun(i, j)
					c += 1
		return c


class Solution:

	def xShape(self, grid):
		ans = 0
		(m, n) = (len(grid), len(grid[0]))
		visited = [[False for _ in range(n)] for _ in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 'X' and (not visited[i][j]):
					self.DFS((i, j), grid, visited, m, n)
					ans += 1
		return ans

	def DFS(self, node, grid, visited, m, n):
		(ci, cj) = node
		visited[ci][cj] = True
		for (ni, nj) in self.get_nbrs(ci, cj, m, n):
			if not visited[ni][nj] and grid[ni][nj] == 'X':
				self.DFS((ni, nj), grid, visited, m, n)

	def get_nbrs(self, pi, pj, m, n):
		res = []
		for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			ni = pi + di
			nj = pj + dj
			if 0 <= ni < m and 0 <= nj < n:
				res.append((ni, nj))
		return res


def dfs(graph, x, y, visited):
	if x < 0 or y < 0 or x >= len(graph) or (y >= len(graph[0])) or visited[x][y] or (graph[x][y] != 'X'):
		return
	visited[x][y] = True
	dfs(graph, x - 1, y, visited)
	dfs(graph, x + 1, y, visited)
	dfs(graph, x, y - 1, visited)
	dfs(graph, x, y + 1, visited)

class Solution:

	def xShape(self, grid):
		visited = [[0] * len(grid[0]) for i in range(len(grid))]
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if not visited[i][j] and grid[i][j] == 'X':
					dfs(grid, i, j, visited)
					ans += 1
		return ans


class Solution:

	def util(self, r, c, row, col, grid):
		if r < 0 or c < 0 or r >= row or (c >= col) or (grid[r][c] != 'X'):
			return
		grid[r][c] = 'O'
		self.util(r + 1, c, row, col, grid)
		self.util(r - 1, c, row, col, grid)
		self.util(r, c + 1, row, col, grid)
		self.util(r, c - 1, row, col, grid)

	def xShape(self, grid):
		count = 0
		row = len(grid)
		col = len(grid[0])
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 'X':
					self.util(i, j, row, col, grid)
					count += 1
		return count


class Solution:

	def xShape(self, grid):
		(rows, cols) = (len(grid), len(grid[0]))
		visited = set()
		groups = 0
		neighbors = ((0, 1), (1, 0), (0, -1), (-1, 0))

		def bfs(r, c):
			if grid[r][c] == 'O':
				return
			for (dr, dc) in neighbors:
				(cur_r, cur_c) = (r + dr, c + dc)
				if cur_r < 0 or cur_r > rows - 1 or cur_c < 0 or (cur_c > cols - 1):
					continue
				if (cur_r, cur_c) in visited:
					continue
				visited.add((cur_r, cur_c))
				if grid[cur_r][cur_c] == 'X':
					bfs(cur_r, cur_c)
		for r in range(rows):
			for c in range(cols):
				if (r, c) in visited:
					continue
				visited.add((r, c))
				if grid[r][c] == 'X':
					groups += 1
					bfs(r, c)
		return groups


from collections import deque

class Solution:

	def BFS(self, i, j, visited, grid, rows, cols):
		queue = deque()
		queue.append((i, j))
		visited[i][j] = True
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		while queue:
			(x, y) = queue.popleft()
			for i in range(4):
				tx = x + dx[i]
				ty = y + dy[i]
				if tx >= 0 and tx < rows and (ty >= 0) and (ty < cols) and (visited[tx][ty] == False) and (grid[tx][ty] == 'X'):
					visited[tx][ty] = True
					queue.append((tx, ty))

	def xShape(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		visited = [[False for i in range(cols)] for i in range(rows)]
		ans = 0
		for i in range(rows):
			for j in range(cols):
				if visited[i][j] == False and grid[i][j] == 'X':
					self.BFS(i, j, visited, grid, rows, cols)
					ans += 1
		return ans


from collections import deque

class Solution:

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

	def xShape(self, grid):
		q = deque()
		ans = 0
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X':
					grid[i][j] = 'O'
					q.append([i, j])
					ans += 1
				while len(q):
					curr = q.popleft()
					x = curr[0]
					y = curr[1]
					for k in range(4):
						nx = x + dx[k]
						ny = y + dy[k]
						if self.isValid(nx, ny, n, m) and grid[nx][ny] == 'X':
							grid[nx][ny] = 'O'
							q.append([nx, ny])
		return ans


from collections import deque

def isInside(i, j, n, m):
	if i >= 0 and i < n and (j >= 0) and (j < m):
		return True
	return False

def getAvailableNeighbors(i, j, n, m, grid):
	dx = [-1, 1, 0, 0]
	dy = [0, 0, 1, -1]
	avail = []
	for w in range(len(dy)):
		x = i + dx[w]
		y = j + dy[w]
		if isInside(x, y, n, m) and grid[x][y] == 'X':
			avail.append((x, y))
	return avail

class Solution:

	def xShape(self, grid):
		q = deque()
		n = len(grid)
		m = len(grid[0])
		shapeCounter = 0
		visited = [[False] * m for i in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X' and (not visited[i][j]):
					shapeCounter += 1
					if not visited[i][j]:
						q.append((i, j))
						visited[i][j] = True
						while q:
							v = q.popleft()
							neigh = getAvailableNeighbors(v[0], v[1], n, m, grid)
							for x in neigh:
								if not visited[x[0]][x[1]]:
									q.append(x)
									visited[x[0]][x[1]] = True
		return shapeCounter


class Solution:

	def dfs(self, row, col, vis, mat, dx, dy):
		n = len(mat)
		m = len(mat[0])
		vis[row][col] = 1
		for i in range(4):
			nrow = row + dx[i]
			ncol = col + dy[i]
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] == 0) and (mat[nrow][ncol] == 'X'):
				vis[nrow][ncol] = 1
				self.dfs(nrow, ncol, vis, mat, dx, dy)

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for i in range(n)]
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		count = 0
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and grid[i][j] == 'X':
					count += 1
					self.dfs(i, j, vis, grid, dx, dy)
		return count


from collections import deque

class Solution:

	def xShape(self, grid):
		rows = len(grid)
		cols = len(grid[0])
		visited = [[False for _ in range(cols)] for __ in range(rows)]
		ans = 0
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 'O' or visited[i][j] is True:
					continue
				visited[i][j] = True
				children = self.valid_child(grid, i, j, visited, rows, cols)
				ans += 1
				self.travel(grid, visited, children, rows, cols)
		return ans

	def travel(self, mat, visited, children, rows, cols):
		q = deque(children)
		while len(q) > 0:
			(i, j) = q.popleft()
			if visited[i][j]:
				continue
			visited[i][j] = True
			new_children = self.valid_child(grid, i, j, visited, rows, cols)
			for child in new_children:
				q.append(child)

	def valid_child(self, mat, i, j, visited, rows, cols):
		ans = []
		if i > 0 and mat[i - 1][j] == 'X' and (visited[i - 1][j] is False):
			ans.append((i - 1, j))
		if j > 0 and mat[i][j - 1] == 'X' and (visited[i][j - 1] is False):
			ans.append((i, j - 1))
		if i < rows - 1 and mat[i + 1][j] == 'X' and (visited[i + 1][j] is False):
			ans.append((i + 1, j))
		if j < cols - 1 and mat[i][j + 1] == 'X' and (visited[i][j + 1] is False):
			ans.append((i, j + 1))
		return ans


class Solution(object):

	def xShape(self, gp):
		visted = set()
		count = 0
		for i in range(len(gp)):
			for j in range(len(gp[0])):
				if (i, j) not in visted and gp[i][j] == 'X':
					self.Dfs(gp, i, j, visted)
					count += 1
		return count

	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] == 'X'):
			return True
		return False

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


class Solution:

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

		def findisland(i, j):
			for (x, y) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				(nr, nc) = (i + x, j + y)
				if nr in range(rows) and nc in range(cols) and (grid[nr][nc] == 'X') and ((nr, nc) not in marked):
					marked.add((nr, nc))
					findisland(nr, nc)
		for i in range(rows):
			for j in range(cols):
				if (i, j) not in marked and grid[i][j] == 'X':
					marked.add((i, j))
					findisland(i, j)
					numIslands += 1
		return numIslands


class Solution:

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

	def dfs(self, row, col, visited, grid):
		visited[row][col] = 1
		delrow = [-1, 0, 1, 0]
		delcol = [0, 1, 0, -1]
		n = len(grid)
		m = len(grid[0])
		for i in range(0, 4):
			nrow = row + delrow[i]
			ncol = col + delcol[i]
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 'X'):
				self.dfs(nrow, ncol, visited, grid)


def dfs(grid, x, y):
	if x < 0 or y < 0 or x >= len(grid) or (len(grid[x]) <= y):
		return
	if grid[x][y] == 'X':
		grid[x][y] = 'O'
		dfs(grid, x + 1, y)
		dfs(grid, x, y + 1)
		dfs(grid, x - 1, y)
		dfs(grid, x, y - 1)

class Solution:

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		ans = 0
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j] == 'X':
					ans += 1
					dfs(grid, i, j)
		return ans


from collections import deque

class Solution:

	def xShape(self, grid):
		(M, N) = (len(grid), len(grid[0]))
		visit = set()
		count = 0
		for i in range(M):
			for j in range(N):
				if grid[i][j] == 'X' and (i, j) not in visit:
					visit.add((i, j))
					self.bfs(grid, i, j, visit)
					count += 1
		return count

	def bfs(self, grid, i, j, visit):
		q = deque([(i, j)])
		while q:
			(r, c) = q.popleft()
			for (dr, dc) in {(-1, 0), (0, -1), (1, 0), (0, 1)}:
				(row, col) = (r + dr, c + dc)
				if row in range(len(grid)) and col in range(len(grid[0])) and (grid[row][col] == 'X') and ((row, col) not in visit):
					q.append((row, col))
					visit.add((row, col))


from collections import deque

class Solution:

	def bfs(self, row, col, vis, grid):
		(n, m) = (len(grid), len(grid[0]))
		q = deque([[row, col]])
		vis[row][col] = 1
		shapes = 0
		moves = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		while q:
			(row, col) = q.popleft()
			for (i, j) in moves:
				nrow = row + i
				ncol = col + j
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (grid[nrow][ncol] == 'X') and (not vis[nrow][ncol]):
					q.append([nrow, ncol])
					vis[nrow][ncol] = 1

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


from collections import deque

class Solution:

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		count = 0
		q = deque()
		visited = set()
		directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X' and (i, j) not in visited:
					count += 1
					q.append((i, j))
					visited.add((i, j))
				while q:
					(r, c) = q.popleft()
					for (k, l) in directions:
						row = k + r
						col = l + c
						if row in range(n) and col in range(m) and (grid[row][col] == 'X') and ((row, col) not in visited):
							q.append((row, col))
							visited.add((row, col))
		return count


from collections import deque

def bfs(i, j, visit, grid):
	visit[i][j] = 1
	q = deque()
	q.append([i, j])
	while q:
		t1 = q.popleft()
		row = t1[0]
		col = t1[1]
		for i in range(-1, 2):
			nrow = row + i
			if nrow >= 0 and nrow < len(grid) and (visit[nrow][col] == 0) and (grid[nrow][col] == 'X'):
				visit[nrow][col] = 1
				q.append([nrow, col])
		for i in range(-1, 2):
			ncol = col + i
			if ncol >= 0 and ncol < len(grid[0]) and (visit[row][ncol] == 0) and (grid[row][ncol] == 'X'):
				visit[row][ncol] = 1
				q.append([row, ncol])

class Solution:

	def xShape(self, grid):
		visit = []
		for i in range(len(grid)):
			visit.append([0 for _ in range(len(grid[0]))])
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visit[i][j] == 0 and grid[i][j] == 'X':
					count += 1
					bfs(i, j, visit, grid)
		return count


class Solution:

	def dfs(self, row, col, grid, visited, R, C):
		if row >= 0 and row < R and (col >= 0) and (col < C) and (grid[row][col] == 'X') and (not visited[row][col]):
			visited[row][col] = True
			dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
			for (dx, dy) in dxy:
				n_row = row + dx
				n_col = col + dy
				self.dfs(n_row, n_col, grid, visited, R, C)

	def xShape(self, grid):
		R = len(grid)
		C = len(grid[0])
		count = 0
		visited = [[False for _ in range(C)] for _ in range(R)]
		for row in range(R):
			for col in range(C):
				if grid[row][col] == 'X' and (not visited[row][col]):
					count += 1
					self.dfs(row, col, grid, visited, R, C)
		return count


class Solution:

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

		def dfs(i, j):
			for k in range(len(a)):
				if i + a[k][0] >= 0 and i + a[k][0] < n and (j + a[k][1] >= 0) and (j + a[k][1] < m):
					if h[i + a[k][0]][j + a[k][1]] == 1:
						continue
					h[i + a[k][0]][j + a[k][1]] = 1
					if grid[i + a[k][0]][j + a[k][1]] == 'X':
						dfs(i + a[k][0], j + a[k][1])
		a = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		h = [[0 for j in range(m)] for i in range(n)]
		ans = 0
		for i in range(n):
			for j in range(m):
				if h[i][j] == 1:
					continue
				if grid[i][j] == 'X' and h[i][j] == 0:
					h[i][j] = 1
					dfs(i, j)
					ans += 1
		return ans


class Solution:

	def xShape(self, grid):
		result = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'X':
					result += 1
					self.dfs(i, j, grid)
		return result

	def dfs(self, row, col, grid):
		grid[row][col] = 'O'
		delRow = [-1, 1, 0, 0]
		delCol = [0, 0, -1, 1]
		for i in range(4):
			nr = row + delRow[i]
			nc = col + delCol[i]
			if nr >= 0 and nr < len(grid) and (nc >= 0) and (nc < len(grid[0])) and (grid[nr][nc] == 'X'):
				self.dfs(nr, nc, grid)


import numpy as np

class Solution:

	def findNextPos(self, grid, visited, start_pos):
		cols = len(grid[0])
		rows = len(grid)
		for r in range(start_pos[0], rows):
			for c in range(0, cols):
				if grid[r][c] == 'X' and (not visited[r][c]):
					return (r, c)
		return None

	def xShape(self, grid):
		cols = len(grid[0])
		rows = len(grid)
		visited = [[0 for c in range(cols)] for r in range(rows)]
		next_pos = (0, 0)
		cnt = 0
		while True:
			next_pos = self.findNextPos(grid, visited, next_pos)
			if next_pos is None:
				break
			cnt += 1
			q = [next_pos]
			visited[next_pos[0]][next_pos[1]] = 1
			grid[next_pos[0]][next_pos[1]] = 0
			while len(q):
				curr_pos = q.pop()
				curr_pos_row = curr_pos[0]
				curr_pos_col = curr_pos[1]
				for r in range(max(0, curr_pos_row - 1), min(rows, curr_pos_row + 2)):
					if grid[r][curr_pos_col] == 'X' and (not visited[r][curr_pos_col]):
						q.append((r, curr_pos_col))
						grid[r][curr_pos_col] = 0
				for c in range(max(0, curr_pos_col - 1), min(cols, curr_pos_col + 2)):
					if grid[curr_pos_row][c] == 'X' and (not visited[curr_pos_row][c]):
						q.append((curr_pos_row, c))
						grid[curr_pos_row][c] = 0
		return cnt


class Solution:

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

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


from collections import deque

def bfs(i, j, visit, grid):
	visit[i][j] = 1
	q = deque()
	q.append([i, j])
	while q:
		t = q.popleft()
		t1 = t[0]
		t2 = t[1]
		for k in range(-1, 2):
			nrow = t1 + k
			if nrow >= 0 and nrow < len(grid) and (visit[nrow][t2] == 0) and (grid[nrow][t2] == 'X'):
				visit[nrow][t2] = 1
				q.append([nrow, t2])
		for k in range(-1, 2):
			ncol = t2 + k
			if ncol >= 0 and ncol < len(grid[0]) and (visit[t1][ncol] == 0) and (grid[t1][ncol] == 'X'):
				visit[t1][ncol] = 1
				q.append([t1, ncol])

class Solution:

	def xShape(self, grid):
		visit = []
		cut = 0
		for i in range(len(grid)):
			visit.append([0 for _ in range(len(grid[0]))])
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'X' and visit[i][j] == 0:
					cut += 1
					bfs(i, j, visit, grid)
		return cut


class Solution:

	def xShape(self, grid):
		rows = len(grid)
		columns = len(grid[0])
		visited = [[False for x in range(columns)] for y in range(rows)]
		total_island = [0]
		for i in range(rows):
			for j in range(columns):
				if not visited[i][j] and grid[i][j] == 'X':
					self.dfs(grid, visited, i, j, rows, columns)
					total_island[0] += 1
		return total_island[0]

	def dfs(self, grid, visited, i, j, rows, columns):
		visited[i][j] = True
		row_check = [-1, 0, 1, 0]
		col_check = [0, -1, 0, 1]
		for k in range(4):
			row = i + row_check[k]
			col = j + col_check[k]
			if (row >= 0 and row < rows) and (col >= 0 and col < columns) and (not visited[row][col]) and (grid[row][col] == 'X'):
				self.dfs(grid, visited, row, col, rows, columns)


class Solution:

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

	def dfs(self, i, j, grid, visited, n, m):
		if i < 0 or j >= m or i >= n or (j < 0):
			return None
		visited[i][j] = True
		newData = [[i - 1, j], [i, j + 1], [i + 1, j], [i, j - 1]]
		for (i, j) in newData:
			if i < 0 or j >= m or i >= n or (j < 0):
				continue
			if not visited[i][j] and grid[i][j] == 'X':
				self.dfs(i, j, grid, visited, n, m)
			visited[i][j] = True
		return None


from collections import deque

class Solution:

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		visited = [[False for i in range(m)] for i in range(n)]
		shapeslength = 0
		for i in range(n):
			for j in range(m):
				if not visited[i][j] and grid[i][j] == 'X':
					shapeslength += 1
					self.bfs(i, j, grid, visited, n, m)
				visited[i][j] = True
		return shapeslength

	def bfs(self, i, j, grid, visited, n, m):
		myQ = deque()
		myQ.append([i, j])
		visited[i][j] = True
		while myQ:
			(i, j) = myQ.popleft()
			newData = [[i - 1, j], [i, j + 1], [i + 1, j], [i, j - 1]]
			for (i, j) in newData:
				if i < 0 or j >= m or i >= n or (j < 0):
					continue
				if not visited[i][j] and grid[i][j] == 'X':
					myQ.append([i, j])
				visited[i][j] = True
		return None


seen = set()

def dfs(i, j, n, m, grid):
	global seen
	if i < 0 or i >= m or j < 0 or (j >= n):
		return
	if (i, j) in seen:
		return
	seen.add((i, j))
	if grid[i][j] == 'X':
		dfs(i + 1, j, n, m, grid)
		dfs(i - 1, j, n, m, grid)
		dfs(i, j + 1, n, m, grid)
		dfs(i, j - 1, n, m, grid)

class Solution:

	def xShape(self, grid):
		global seen
		count = 0
		(m, n) = (len(grid), len(grid[0]))
		for i in range(0, m):
			for j in range(0, n):
				if (i, j) not in seen and grid[i][j] == 'X':
					dfs(i, j, n, m, grid)
					count += 1
		seen.clear()
		return count


class Solution:

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

	def dfs(self, grid, i, j, n, m):
		grid[i][j] = 'x'
		for (x, y) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
			if 0 <= i + x < n and 0 <= j + y < m and (grid[i + x][j + y] == 'X'):
				self.dfs(grid, i + x, j + y, n, m)


class Solution:

	def __init__(self):
		self.visited_loc = {}
		self.tot_count = 0

	def xShape(self, grid):
		self.row_len = len(grid)
		self.col_len = len(grid[0])

		def searchBFS(loc_row, loc_col):
			if loc_row + 1 < self.row_len and (loc_row + 1, loc_col) not in self.visited_loc and (grid[loc_row + 1][loc_col] == 'X'):
				self.visited_loc[loc_row + 1, loc_col] = 1
				searchBFS(loc_row + 1, loc_col)
			if loc_row - 1 >= 0 and (loc_row - 1, loc_col) not in self.visited_loc and (grid[loc_row - 1][loc_col] == 'X'):
				self.visited_loc[loc_row - 1, loc_col] = 1
				searchBFS(loc_row - 1, loc_col)
			if loc_col + 1 < self.col_len and (loc_row, loc_col + 1) not in self.visited_loc and (grid[loc_row][loc_col + 1] == 'X'):
				self.visited_loc[loc_row, loc_col + 1] = 1
				searchBFS(loc_row, loc_col + 1)
			if loc_col - 1 >= 0 and (loc_row, loc_col - 1) not in self.visited_loc and (grid[loc_row][loc_col - 1] == 'X'):
				self.visited_loc[loc_row, loc_col - 1] = 1
				searchBFS(loc_row, loc_col - 1)
		for row in range(self.row_len):
			for col in range(self.col_len):
				if (row, col) in self.visited_loc:
					continue
				self.visited_loc[row, col] = 1
				if grid[row][col] == 'X':
					self.tot_count += 1
					searchBFS(row, col)
		return self.tot_count


class Solution:

	def xShape(self, grid):
		visited = [[True] * len(grid[0]) for _ in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 'X':
					visited[i][j] = False
		moves = [[1, 0], [0, 1], [-1, 0], [0, -1]]

		def dfs(x, y):
			for (mx, my) in moves:
				(nx, ny) = (x + mx, y + my)
				if nx >= 0 and nx < len(grid) and (ny >= 0) and (ny < len(grid[0])) and (visited[nx][ny] == False):
					visited[nx][ny] = True
					dfs(nx, ny)
		count = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if not visited[i][j]:
					visited[i][j] = True
					count += 1
					dfs(i, j)
		return count


class Solution:

	def xShape(self, grid):
		dr = [1, -1, 0, 0]
		dc = [0, 0, -1, 1]
		n = len(grid)
		m = len(grid[0])

		def bfs(cr, cc):
			l1 = [[cr, cc]]
			grid[cr][cc] = '0'
			l2 = []
			while len(l1) != 0:
				for i in l1:
					(cr, cc) = i
					for j in range(4):
						nr = cr + dr[j]
						nc = cc + dc[j]
						if nr >= 0 and nr < n and (nc >= 0) and (nc < m):
							if grid[nr][nc] == 'X':
								grid[nr][nc] = 'O'
								l2.append([nr, nc])
				l1 = l2[:]
				l2 = []
		ans = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X':
					bfs(i, j)
					ans += 1
		return ans


class Solution:

	def xShape(self, grid):
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for i in range(n)]
		dx = [1, -1, 0, 0]
		dy = [0, 0, 1, -1]

		def is_valid(x, y):
			if x < 0 or y < 0 or x >= n or (y >= m) or vis[x][y] or (grid[x][y] != 'X'):
				return 0
			return 1
		ans = 0
		for i in range(n):
			for j in range(m):
				if vis[i][j] or grid[i][j] != 'X':
					continue
				ans += 1
				stack = [(i, j)]
				while stack:
					(x, y) = stack.pop()
					for k in range(4):
						(nx, ny) = (x + dx[k], y + dy[k])
						if is_valid(nx, ny):
							vis[nx][ny] = 1
							stack.append((nx, ny))
		return ans


class Solution:

	def xShape(self, grid):
		visited = set()
		count = 0
		directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]

		def bfs(r, c):
			if r in range(len(grid)) and c in range(len(grid[0])) and ((r, c) not in visited) and (grid[r][c] == 'X'):
				visited.add((r, c))
				bfs(r + 1, c)
				bfs(r - 1, c)
				bfs(r, c + 1)
				bfs(r, c - 1)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if (i, j) not in visited and grid[i][j] == 'X':
					bfs(i, j)
					count += 1
		return count


def isvalid(A, nx, ny):
	N = len(A)
	M = len(A[0])
	if nx >= 0 and nx < N and (ny >= 0) and (ny < M):
		return True
	return False

def dfs(A, x, y):
	A[x][y] = '^'
	dx = [1, -1, 0, 0]
	dy = [0, 0, 1, -1]
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if isvalid(A, nx, ny) and A[nx][ny] == 'X':
			dfs(A, nx, ny)

class Solution:

	def xShape(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] == 'X':
					dfs(A, i, j)
					ans += 1
		return ans


class Solution:

	def xShape(self, grid):
		vis = [[0 for _ in range(len(grid[0]))] for __ in range(len(grid))]
		c = 0
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if grid[i][j] == 'X' and vis[i][j] != 1:
					self.bfs(vis, grid, i, j)
					c = c + 1
		return c

	def bfs(self, vis, grid, i, j):
		q = [[i, j]]
		while q:
			x = q.pop(0)
			r = x[0]
			c = x[1]
			vis[r][c] = 1
			de = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]
			for i in de:
				ro = i[0]
				co = i[1]
				if ro >= 0 and co >= 0 and (ro < len(grid)) and (co < len(grid[0])) and (vis[ro][co] != 1):
					if grid[ro][co] == 'X':
						vis[ro][co] = 1
						q.append([ro, co])


def dfs(i, j, n, m, grid):
	if i < 0 or j < 0 or i == n or (j == m) or (grid[i][j] == 'O'):
		return None
	else:
		grid[i][j] = 'O'
		dfs(i + 1, j, n, m, grid)
		dfs(i - 1, j, n, m, grid)
		dfs(i, j + 1, n, m, grid)
		dfs(i, j - 1, n, m, grid)
		return

class Solution:

	def xShape(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] == 'X':
					count += 1
					dfs(i, j, n, m, grid)
		return count


class Solution:

	def xShape(self, grid):

		def xdfs(a, b):
			for (u, v) in move:
				x = a + u
				y = b + v
				if 0 <= x < r and 0 <= y < c and (visited[x][y] != 1) and (grid[x][y] == 'X'):
					visited[x][y] = 1
					xdfs(x, y)
		r = len(grid)
		c = len(grid[0])
		move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		visited = [[0 for _ in range(c)] for _ in range(r)]
		cnt_x = 0
		for i in range(r):
			for j in range(c):
				if visited[i][j] != 1 and grid[i][j] == 'X':
					visited[i][j] = 1
					xdfs(i, j)
					cnt_x += 1
		return cnt_x


class Solution:

	def xShape(self, grid):
		L = len(grid)
		W = len(grid[0])

		def dfs(i, j):
			if i < 0 or j < 0 or i >= L or (j >= W):
				return
			if grid[i][j] == 'O':
				return
			grid[i][j] = 'O'
			dfs(i - 1, j)
			dfs(i + 1, j)
			dfs(i, j + 1)
			dfs(i, j - 1)
		count = 0
		for i in range(L):
			for j in range(W):
				if grid[i][j] != 'O':
					dfs(i, j)
					count += 1
		return count


class Solution:

	def dfs(self, grid, i, j, r, c):
		if i < 0 or j < 0 or i >= r or (j >= c) or (grid[i][j] != 'X'):
			return
		grid[i][j] = 2
		self.dfs(grid, i + 1, j, r, c)
		self.dfs(grid, i - 1, j, r, c)
		self.dfs(grid, i, j - 1, r, c)
		self.dfs(grid, i, j + 1, r, c)

	def xShape(self, grid):
		count = 0
		r = len(grid)
		c = len(grid[0])
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 'X':
					self.dfs(grid, i, j, r, c)
					count += 1
		return count


class Solution:

	def xShape(self, grid):
		row = len(grid)
		col = len(grid[0])
		visit = [[False for i in range(col)] for i in range(row)]
		count = [0]
		for i in range(row):
			for j in range(col):
				if visit[i][j] == False and grid[i][j] == 'X':
					self.rec(visit, i, j, row, col)
					count[0] += 1
		return count[0]

	def safe(self, i, j, row, col, visit):
		return i >= 0 and i < row and (j >= 0) and (j < col) and (not visit[i][j]) and (grid[i][j] == 'X')

	def rec(self, visit, i, j, row, col):
		visit[i][j] = True
		r = [-1, 1, 0, 0]
		c = [0, 0, -1, 1]
		for k in range(4):
			if self.safe(i + r[k], j + c[k], row, col, visit):
				self.rec(visit, i + r[k], j + c[k], row, col)


class Solution:

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

		def dfs(i, j):
			if i < 0 or i > n - 1 or j < 0 or (j > m - 1) or (grid[i][j] != 'X'):
				return
			grid[i][j] = '2'
			dfs(i + 1, j)
			dfs(i - 1, j)
			dfs(i, j - 1)
			dfs(i, j + 1)
		cnt = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 'X':
					dfs(i, j)
					cnt += 1
		return cnt


class Solution:

	def xShape(self, grid):
		count = 0
		visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visited[i][j] is True:
					continue
				if grid[i][j] == 'X':
					count += 1
					self.dfs(grid, visited, i, j)
		return count

	def dfs(self, grid, visited, i, j):
		nodes_to_explore = [[i, j]]
		while nodes_to_explore:
			(cur_i, cur_j) = nodes_to_explore.pop()
			visited[cur_i][cur_j] = True
			next_nodes = self.get_unvisited_nbrs(visited, cur_i, cur_j)
			for node in next_nodes:
				(temp_i, temp_j) = node
				if grid[temp_i][temp_j] == 'X':
					nodes_to_explore.append([temp_i, temp_j])

	def get_unvisited_nbrs(self, visited, i, j):
		nodes = []
		if i > 0 and (not visited[i - 1][j]):
			nodes.append([i - 1, j])
		if j > 0 and (not visited[i][j - 1]):
			nodes.append([i, j - 1])
		if j < len(visited[0]) - 1 and (not visited[i][j + 1]):
			nodes.append([i, j + 1])
		if i < len(visited) - 1 and (not visited[i + 1][j]):
			nodes.append([i + 1, j])
		return nodes