Given a matrix mat of size N x M where every element is either O or X.
Replace all O with X that are surrounded by X.
A O (or a set of O) is considered to be surrounded by X if there are X at locations just below, just above, just left and just right of it.
Example 1:
Input: n = 5, m = 4
mat = {{'X', 'X', 'X', 'X'}, 
       {'X', 'O', 'X', 'X'}, 
       {'X', 'O', 'O', 'X'}, 
       {'X', 'O', 'X', 'X'}, 
       {'X', 'X', 'O', 'O'}}
Output: ans = {{'X', 'X', 'X', 'X'}, 
               {'X', 'X', 'X', 'X'}, 
               {'X', 'X', 'X', 'X'}, 
               {'X', 'X', 'X', 'X'}, 
               {'X', 'X', 'O', 'O'}}
Explanation: Following the rule the above 
matrix is the resultant matrix. 
Your Task:
You do not need to read input or print anything. Your task is to complete the function fill() which takes n, m and mat as input parameters ad returns a 2D array representing the resultant matrix.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1 ≤ n, m ≤ 500

Difficulty: MEDIUM
Tags: Matrices

Graph algorithms

Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)

Starter code:
#User function Template for python3



class Solution:

    def fill(self, n, m, mat):

        # code here

Solutions:
class Solution:

	def fill(self, n, m, mat):

		def dfs(row, col, visited, mat, r, c):
			visited[row][col] = 1
			for i in range(4):
				nrow = row + r[i]
				ncol = col + c[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] != 1) and (mat[nrow][ncol] == 'O'):
					dfs(nrow, ncol, visited, mat, r, c)
		r = [-1, 0, 1, 0]
		c = [0, 1, 0, -1]
		visited = [[0] * m for i in range(n)]
		for i in range(m):
			if visited[0][i] != 1 and mat[0][i] == 'O':
				dfs(0, i, visited, mat, r, c)
			if visited[n - 1][i] != 1 and mat[n - 1][i] == 'O':
				dfs(n - 1, i, visited, mat, r, c)
		for i in range(n):
			if visited[i][0] != 1 and mat[i][0] == 'O':
				dfs(i, 0, visited, mat, r, c)
			if visited[i][m - 1] != 1 and mat[i][m - 1] == 'O':
				dfs(i, m - 1, visited, mat, r, c)
		for i in range(n):
			for j in range(m):
				if visited[i][j] != 1 and mat[i][j] == 'O':
					mat[i][j] = 'X'
		return mat


class Solution:

	def dfs(self, row, col, mat, vis, dr, dc):
		vis[row][col] = 1
		for i in range(4):
			nrow = row + dr[i]
			ncol = col + dc[i]
			if nrow >= 0 and nrow < len(mat) and (ncol >= 0) and (ncol < len(mat[0])) and (vis[nrow][ncol] == 0) and (mat[nrow][ncol] == 'O'):
				self.dfs(nrow, ncol, mat, vis, dr, dc)

	def fill(self, n, m, mat):
		vis = [[0 for _ in range(m)] for _ in range(n)]
		dr = [-1, 0, 1, 0]
		dc = [0, -1, 0, 1]
		for j in range(m):
			if vis[0][j] == 0 and mat[0][j] == 'O':
				self.dfs(0, j, mat, vis, dr, dc)
			if vis[n - 1][j] == 0 and mat[n - 1][j] == 'O':
				self.dfs(n - 1, j, mat, vis, dr, dc)
		for i in range(n):
			if vis[i][0] == 0 and mat[i][0] == 'O':
				self.dfs(i, 0, mat, vis, dr, dc)
			if vis[i][m - 1] == 0 and mat[i][m - 1] == 'O':
				self.dfs(i, m - 1, mat, vis, dr, dc)
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and mat[i][j] == 'O':
					mat[i][j] = 'X'
		return mat


class Solution:

	def fill(self, M, N, mat):

		def floodFillUtil(mat, x, y, prevV, newV):
			if x < 0 or x >= M or y < 0 or (y >= N):
				return
			if mat[x][y] != prevV:
				return
			mat[x][y] = newV
			floodFillUtil(mat, x + 1, y, prevV, newV)
			floodFillUtil(mat, x - 1, y, prevV, newV)
			floodFillUtil(mat, x, y + 1, prevV, newV)
			floodFillUtil(mat, x, y - 1, prevV, newV)

		def replaceSurrounded(mat):
			for i in range(M):
				for j in range(N):
					if mat[i][j] == 'O':
						mat[i][j] = '-'
			for i in range(M):
				if mat[i][0] == '-':
					floodFillUtil(mat, i, 0, '-', 'O')
			for i in range(M):
				if mat[i][N - 1] == '-':
					floodFillUtil(mat, i, N - 1, '-', 'O')
			for i in range(N):
				if mat[0][i] == '-':
					floodFillUtil(mat, 0, i, '-', 'O')
			for i in range(N):
				if mat[M - 1][i] == '-':
					floodFillUtil(mat, M - 1, i, '-', 'O')
			for i in range(M):
				for j in range(N):
					if mat[i][j] == '-':
						mat[i][j] = 'X'
		replaceSurrounded(mat)
		return mat


class Solution:

	def fill(self, n, m, mat):
		vis = [[False for i in range(m)] for j in range(n)]
		res = [[0 for i in range(m)] for j in range(n)]
		queue = []
		for i in range(m):
			if mat[0][i] == 'O':
				queue.append([0, i])
				vis[0][i] = 1
			if mat[-1][i] == 'O':
				queue.append([n - 1, i])
				vis[-1][i] = 1
		for i in range(1, n - 1):
			if mat[i][0] == 'O':
				queue.append([i, 0])
				vis[i][0] = 1
			if mat[i][m - 1] == 'O':
				queue.append([i, m - 1])
				vis[i][m - 1] = 1
		while len(queue) > 0:
			(r, s) = queue.pop(0)
			res[r][s] = 'O'
			dirx = [-1, 1, 0, 0]
			diry = [0, 0, -1, 1]
			for ele in range(4):
				newx = r + dirx[ele]
				newy = s + diry[ele]
				if 0 <= newx < len(mat) and 0 <= newy < len(mat[0]) and (vis[newx][newy] == False) and (mat[newx][newy] == 'O'):
					queue.append([newx, newy])
					vis[newx][newy] = 1
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if res[i][j] == 0:
					res[i][j] = 'X'
		return res


class Solution:

	def fill(self, n, m, mat):
		visited = [[0 for i in range(m)] for j in range(n)]

		def dfs(visited, row, col, mat):
			row_del = [-1, 1, 0, 0]
			col_del = [0, 0, -1, 1]
			visited[row][col] = 1
			for i in range(4):
				new_row = row + row_del[i]
				new_col = col + col_del[i]
				if new_row < n and new_col < m and (new_row > -1) and (new_col > -1) and (mat[new_row][new_col] == 'O') and (visited[new_row][new_col] == 0):
					dfs(visited, new_row, new_col, mat)
		for i in range(m):
			if mat[0][i] == 'O' and visited[0][i] == 0:
				dfs(visited, 0, i, mat)
			if mat[n - 1][i] == 'O' and visited[n - 1][i] == 0:
				dfs(visited, n - 1, i, mat)
		for i in range(n):
			if mat[i][0] == 'O' and visited[i][0] == 0:
				dfs(visited, i, 0, mat)
			if mat[i][m - 1] == 'O' and visited[i][m - 1] == 0:
				dfs(visited, i, m - 1, mat)
		for i in range(n):
			for j in range(m):
				if visited[i][j] == 0 and mat[i][j] == 'O':
					mat[i][j] = 'X'
		return mat


class Solution:

	def fill(self, n, m, mat):
		res = mat
		n = len(mat)
		m = len(mat[0])
		if n == 1 or n == 2:
			return mat
		vis = []
		for i in range(n):
			vis.append([0] * m)
		for i in range(n):
			for j in range(m):
				if i == 0 or (i == n - 1 and 0 <= j < m):
					if mat[i][j] == 'O':
						vis[i][j] = 1
						self.dfs(i, j, mat, vis)
				if j == 0 or (j == m - 1 and 0 <= i < n):
					if mat[i][j] == 'O':
						vis[i][j] = 1
						self.dfs(i, j, mat, vis)
		for x in range(1, n - 1):
			for y in range(1, m - 1):
				if mat[x][y] == 'O' and vis[x][y] != 1:
					res[x][y] = 'X'
		return res

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


from collections import deque

class Solution:

	def fill(self, n, m, mat):
		boundry = set()
		vis = set()
		q = deque([])
		ans = [[1 for i in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				if (i == 0 or i == n - 1 or j == 0 or (j == m - 1)) and mat[i][j] == 'O':
					boundry.add((i, j))
					q.append((i, j))
					vis.add((i, j))
		while q:
			(row, col) = q.popleft()
			dRow = [-1, 1, 0, 0]
			dCol = [0, 0, -1, 1]
			for i in range(4):
				nr = row + dRow[i]
				nc = col + dCol[i]
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and ((nr, nc) not in vis) and (mat[nr][nc] == 'O'):
					vis.add((nr, nc))
					boundry.add((nr, nc))
					q.append((nr, nc))
		for i in range(n):
			for j in range(m):
				if (i, j) in boundry:
					ans[i][j] = 'O'
				else:
					ans[i][j] = 'X'
		return ans


class Solution:

	def fill(self, n, m, a):
		q = []
		for i in range(n):
			if a[i][0] == 'O':
				q.append((i, 0))
			if a[i][m - 1] == 'O':
				q.append((i, m - 1))
		for j in range(m):
			if a[0][j] == 'O':
				q.append((0, j))
			if a[n - 1][j] == 'O':
				q.append((n - 1, j))
		while len(q) != 0:
			(i, j) = q.pop(0)
			a[i][j] = '1'
			for k in [-1, 1]:
				if i + k >= 0 and i + k < n and (a[i + k][j] == 'O'):
					q.append((i + k, j))
				if j + k >= 0 and j + k < m and (a[i][j + k] == 'O'):
					q.append((i, j + k))
		for i in range(n):
			for j in range(m):
				if a[i][j] == '1':
					a[i][j] = 'O'
				elif a[i][j] == 'O':
					a[i][j] = 'X'
		return a


class Solution:

	def fill(self, n, m, mat):
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'O':
					mat[i][j] = '-'
		for i in range(n):
			if mat[i][0] == '-':
				self.helper(mat, i, 0, '-', 'O')
		for i in range(n):
			if mat[i][m - 1] == '-':
				self.helper(mat, i, m - 1, '-', 'O')
		for i in range(m):
			if mat[0][i] == '-':
				self.helper(mat, 0, i, '-', 'O')
		for i in range(m):
			if mat[n - 1][i] == '-':
				self.helper(mat, n - 1, i, '-', 'O')
		for i in range(n):
			for j in range(m):
				if mat[i][j] == '-':
					mat[i][j] = 'X'
		return mat

	def helper(self, mat, x, y, prevV, newV):
		if x < 0 or x >= n or y < 0 or (y >= m):
			return
		if mat[x][y] != prevV:
			return
		mat[x][y] = newV
		self.helper(mat, x + 1, y, prevV, newV)
		self.helper(mat, x - 1, y, prevV, newV)
		self.helper(mat, x, y + 1, prevV, newV)
		self.helper(mat, x, y - 1, prevV, newV)


from collections import deque

class Solution:

	def fill(self, n, m, mat):
		vis = [[0 for j in range(m)] for i in range(n)]

		def dfs(r, c):
			vis[r][c] = 1
			delr = [0, 1, 0, -1]
			delc = [1, 0, -1, 0]
			for i in range(4):
				nr = delr[i] + r
				nc = delc[i] + c
				if nr >= 0 and nc >= 0 and (nr < n) and (nc < m) and (vis[nr][nc] != 1) and (mat[nr][nc] == 'O'):
					dfs(nr, nc)
		for i in range(n):
			if vis[i][0] != 1 and mat[i][0] == 'O':
				dfs(i, 0)
			if vis[i][m - 1] != 1 and mat[i][m - 1] == 'O':
				dfs(i, m - 1)
		for j in range(m):
			if vis[0][j] != 1 and mat[0][j] == 'O':
				dfs(0, j)
			if vis[n - 1][j] != 1 and mat[n - 1][j] == 'O':
				dfs(n - 1, j)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'O' and vis[i][j] == 0:
					mat[i][j] = 'X'
		return mat


class Solution:

	def fill(self, n, m, mat):

		def cap(r, c):
			if r < 0 or c < 0 or r >= n or (c >= m) or (mat[r][c] != 'O'):
				return
			mat[r][c] = 'T'
			cap(r + 1, c)
			cap(r - 1, c)
			cap(r, c + 1)
			cap(r, c - 1)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'O' and (i in [0, n - 1] or j in [0, m - 1]):
					cap(i, j)
		for r in range(n):
			for c in range(m):
				if mat[r][c] == 'O':
					mat[r][c] = 'X'
		for r in range(n):
			for c in range(m):
				if mat[r][c] == 'T':
					mat[r][c] = 'O'
		return mat


class Solution:

	def fill(self, n, m, mat):
		visited = [[0 for i in range(m)] for j in range(n)]
		ans = mat.copy()

		def dfs(row, col):
			visited[row][col] = 1
			path = [(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)]
			for (nrow, ncol) in path:
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] == 0) and (mat[nrow][ncol] == 'O'):
					dfs(nrow, ncol)
		for i in range(n):
			if mat[i][0] == 'O' and visited[i][0] == 0:
				dfs(i, 0)
			if mat[i][-1] == 'O' and visited[i][m - 1] == 0:
				dfs(i, m - 1)
		for j in range(m):
			if mat[0][j] == 'O' and visited[0][j] == 0:
				dfs(0, j)
			if mat[n - 1][j] == 'O' and visited[n - 1][j] == 0:
				dfs(n - 1, j)
		for i in range(n):
			for j in range(m):
				if ans[i][j] == 'O' and visited[i][j] == 0:
					ans[i][j] = 'X'
		return ans


class Solution:

	def dfs(self, r, c, mat, n, m, vis):
		vis[r][c] = 1
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		for i in range(4):
			nr = r + dr[i]
			nc = c + dc[i]
			if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (vis[nr][nc] == 0) and (mat[nr][nc] == 'O'):
				self.dfs(nr, nc, mat, n, m, vis)

	def fill(self, n, m, mat):
		vis = [[0 for j in range(m)] for i in range(n)]
		for j in range(m):
			if mat[0][j] == 'O' and vis[0][j] == 0:
				self.dfs(0, j, mat, n, m, vis)
			if mat[n - 1][j] == 'O' and vis[n - 1][j] == 0:
				self.dfs(n - 1, j, mat, n, m, vis)
		for i in range(n):
			if mat[i][0] == 'O' and vis[i][0] == 0:
				self.dfs(i, 0, mat, n, m, vis)
			if mat[i][m - 1] == 'O' and vis[i][m - 1] == 0:
				self.dfs(i, m - 1, mat, n, m, vis)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'O' and vis[i][j] == 0:
					mat[i][j] = 'X'
		return mat


class Solution:

	def fill(self, n, m, mat):
		arr = []
		neighbors = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		for i in range(n):
			for j in range(m):
				if (i == 0 or j == 0 or i == n - 1 or (j == m - 1)) and mat[i][j] == 'O':
					arr.append([i, j])
		visited = [[0] * m for _ in range(n)]
		for i in arr:
			row = i[0]
			col = i[1]
			q = []
			ptr = 0
			if visited[row][col] == 0:
				q.append(i)
				visited[row][col] = 1
				mat[row][col] = 1
				while ptr < len(q):
					row = q[ptr][0]
					col = q[ptr][1]
					for x in neighbors:
						try:
							if row - x[0] >= 0 and col - x[1] >= 0 and (visited[row - x[0]][col - x[1]] == 0) and (mat[row - x[0]][col - x[1]] == 'O'):
								q.append([row - x[0], col - x[1]])
								visited[row - x[0]][col - x[1]] = 1
								mat[row - x[0]][col - x[1]] = 1
						except:
							pass
					ptr += 1
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					mat[i][j] = 'O'
				else:
					mat[i][j] = 'X'
		return mat


class Solution:

	def __dfs__(self, visited, final_ans, root, row, col, rows, columns):
		visited[row][col] = True
		nodes_to_visit = [(row - 1, col), (row + 1, col), (row, col + 1), (row, col - 1)]
		for (temp_row, temp_col) in nodes_to_visit:
			if 0 <= temp_row < rows and 0 <= temp_col < columns and (not visited[temp_row][temp_col]) and (final_ans[temp_row][temp_col] == 'O'):
				self.__dfs__(visited, final_ans, root, temp_row, temp_col, rows, columns)

	def fill(self, rows, columns, grid):
		final_ans = [row[:] for row in grid]
		visited_arr = [[False for _ in range(columns)] for _ in range(rows)]
		for row in range(rows):
			for col in range(columns):
				if not visited_arr[row][col] and grid[row][col] == 'O' and (row == rows - 1 or row == 0 or col == 0 or (col == columns - 1)):
					self.__dfs__(visited_arr, final_ans, grid[row][col], row, col, rows, columns)
		for i in range(rows):
			for j in range(columns):
				if final_ans[i][j] == 'O' and (not visited_arr[i][j]):
					final_ans[i][j] = 'X'
		return final_ans


from collections import deque

class Solution:

	def dfs(self, i, j, vis, mat):
		(n, m) = (len(mat), len(mat[0]))
		vis[i][j] = 1
		(dx, dy) = ([-1, 0, 1, 0], [0, -1, 0, 1])
		for k in range(4):
			(nx, ny) = (i + dx[k], j + dy[k])
			if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (vis[nx][ny] == 0) and (mat[nx][ny] == 'O'):
				self.dfs(nx, ny, vis, mat)

	def fill(self, n, m, mat):
		vis = [[0] * m for _ in range(n)]
		ans = mat
		q = deque()
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0 or i == n - 1 or (j == m - 1):
					if vis[i][j] == 0 and ans[i][j] == 'O':
						q.append((i, j))
						vis[i][j] = 1
		while q:
			(i, j) = q.popleft()
			(dx, dy) = ([-1, 0, 1, 0], [0, -1, 0, 1])
			for k in range(4):
				(nx, ny) = (i + dx[k], j + dy[k])
				if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (vis[nx][ny] == 0) and (ans[nx][ny] == 'O'):
					q.append((nx, ny))
					vis[nx][ny] = 1
		for i in range(n):
			for j in range(m):
				if ans[i][j] == 'O' and vis[i][j] == 0:
					ans[i][j] = 'X'
		return ans


class Solution:

	def dfs(self, i, j, vis, mat):
		(n, m) = (len(mat), len(mat[0]))
		vis[i][j] = 1
		(dx, dy) = ([-1, 0, 1, 0], [0, -1, 0, 1])
		for k in range(4):
			(nx, ny) = (i + dx[k], j + dy[k])
			if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (vis[nx][ny] == 0) and (mat[nx][ny] == 'O'):
				self.dfs(nx, ny, vis, mat)

	def fill(self, n, m, mat):
		vis = [[0] * m for _ in range(n)]
		ans = mat
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0 or i == n - 1 or (j == m - 1):
					if ans[i][j] == 'O' and vis[i][j] == 0:
						self.dfs(i, j, vis, mat)
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and ans[i][j] == 'O':
					ans[i][j] = 'X'
		return ans


class Solution:

	def fill(self, n, m, board):

		def dfs(m, n, delcol, delrow, board, vis, row, col):
			vis[row][col] = 1
			for i in range(4):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] == 0) and (board[nrow][ncol] == 'O'):
					dfs(m, n, delcol, delrow, board, vis, nrow, ncol)
		vis = [[0 for j in range(m)] for i in range(n)]
		delrow = [-1, 0, 1, 0]
		delcol = [0, 1, 0, -1]
		for j in range(m):
			if vis[0][j] == 0 and board[0][j] == 'O':
				dfs(m, n, delcol, delrow, board, vis, 0, j)
			if vis[n - 1][j] == 0 and board[n - 1][j] == 'O':
				dfs(m, n, delcol, delrow, board, vis, n - 1, j)
		for i in range(n):
			if vis[i][0] == 0 and board[i][0] == 'O':
				dfs(m, n, delcol, delrow, board, vis, i, 0)
			if vis[i][m - 1] == 0 and board[i][m - 1] == 'O':
				dfs(m, n, delcol, delrow, board, vis, i, m - 1)
		for i in range(n):
			for j in range(m):
				if board[i][j] == 'O' and vis[i][j] == 0:
					board[i][j] = 'X'
		return board


class Solution:
	ans = 1

	def gen(self, i, j, n, m, mat, visited):
		visited[i][j] = 1
		if i - 1 >= 0 and visited[i - 1][j] == 0 and (mat[i - 1][j] == 'O'):
			visited[i - 1][j] = 1
			self.gen(i - 1, j, n, m, mat, visited)
		if i + 1 < n and visited[i + 1][j] == 0 and (mat[i + 1][j] == 'O'):
			visited[i + 1][j] = 1
			self.gen(i + 1, j, n, m, mat, visited)
		if j - 1 >= 0 and visited[i][j - 1] == 0 and (mat[i][j - 1] == 'O'):
			visited[i][j - 1] = 1
			self.gen(i, j - 1, n, m, mat, visited)
		if j + 1 < m and visited[i][j + 1] == 0 and (mat[i][j + 1] == 'O'):
			visited[i][j + 1] = 1
			self.gen(i, j + 1, n, m, mat, visited)
		return

	def fill(self, n, m, mat):
		q = []
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'O' and (i == 0 or j == 0 or i == n - 1 or (j == m - 1)):
					q.append([i, j])
		visited = []
		for i in range(n):
			arr = []
			for j in range(m):
				arr.append(0)
			visited.append(arr)
		for i in q:
			self.gen(i[0], i[1], n, m, mat, visited)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'O' and visited[i][j] == 0:
					mat[i][j] = 'X'
		return mat


class Solution:

	def fill(self, n, m, mat):
		direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		visited = [[0 for i in range(m)] for j in range(n)]

		def dfs(row, col):
			visited[row][col] = 1
			for dir in direction:
				r = row + dir[0]
				c = col + dir[1]
				if (r >= 0 and r < n) and (c >= 0 and c < m) and (not visited[r][c]):
					if mat[r][c] == 'O':
						dfs(r, c)
		for i in range(n):
			if mat[i][0] == 'O' and visited[i][0] == 0:
				dfs(i, 0)
		for i in range(n):
			if mat[i][m - 1] == 'O' and visited[i][m - 1] == 0:
				dfs(i, m - 1)
		for j in range(m):
			if mat[0][j] == 'O' and visited[0][j] == 0:
				dfs(0, j)
		for j in range(m):
			if mat[n - 1][j] == 'O' and visited[n - 1][j] == 0:
				dfs(n - 1, j)
		for i in range(n):
			for j in range(m):
				if visited[i][j] == 1:
					visited[i][j] = 'O'
				else:
					visited[i][j] = 'X'
		return visited


class Solution:

	def fill(self, n, m, mat):
		directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]

		def dfs(row, col):
			if row >= 0 and row < n and (col >= 0) and (col < m) and (mat[row][col] == 'O'):
				mat[row][col] = 'NO'
				for dir in directions:
					newRow = row + dir[0]
					newCol = col + dir[1]
					dfs(newRow, newCol)
		for i in range(n):
			dfs(i, 0)
		for i in range(n):
			dfs(i, m - 1)
		for i in range(m):
			dfs(0, i)
		for i in range(m):
			dfs(n - 1, i)
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 'NO':
					mat[i][j] = 'O'
				else:
					mat[i][j] = 'X'
		return mat


class Solution:

	def DFS(self, row, col, mat, visited, n, m):
		visited[row][col] = True
		delta_col = [-1, 0, 1, 0]
		delta_row = [0, 1, 0, -1]
		for i in range(0, 4):
			nrow = row + delta_row[i]
			ncol = col + delta_col[i]
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (not visited[nrow][ncol]) and (mat[nrow][ncol] == 'O'):
				self.DFS(nrow, ncol, mat, visited, n, m)

	def fill(self, n, m, mat):
		visited = [[False for i in range(0, m)] for j in range(0, n)]
		for j in range(0, m):
			if not visited[0][j] and mat[0][j] == 'O':
				self.DFS(0, j, mat, visited, n, m)
			if not visited[n - 1][j] and mat[n - 1][j] == 'O':
				self.DFS(n - 1, j, mat, visited, n, m)
		for i in range(0, n):
			if not visited[i][0] and mat[i][0] == 'O':
				self.DFS(i, 0, mat, visited, n, m)
			if not visited[i][m - 1] and mat[i][m - 1] == 'O':
				self.DFS(i, m - 1, mat, visited, n, m)
		for i in range(0, n):
			for j in range(0, m):
				if not visited[i][j] and mat[i][j] == 'O':
					mat[i][j] = 'X'
		return mat


import numpy as np

class Solution:

	def fill(self, n, m, mat):
		board = mat

		def capture(board, i, j):
			if i < 0 or i >= len(board) or j < 0 or (j >= len(board[0])):
				return
			if board[i][j] == 'O' and visited[i][j] == 0:
				visited[i][j] = 1
				capture(board, i - 1, j)
				capture(board, i + 1, j)
				capture(board, i, j - 1)
				capture(board, i, j + 1)
		(rows, cols) = (len(board), len(board[0]))
		visited = np.zeros((rows, cols), dtype=np.int8)
		for i in range(rows):
			if board[i][0] == 'O' and visited[i, 0] != 1:
				capture(board, i, 0)
			if board[i][cols - 1] == 'O' and visited[i, cols - 1] != 1:
				capture(board, i, cols - 1)
		for j in range(cols):
			if board[0][j] == 'O' and visited[0, j] != 1:
				capture(board, 0, j)
			if board[rows - 1][j] == 'O' and visited[rows - 1, j] != 1:
				capture(board, rows - 1, j)
		for i in range(rows):
			for j in range(cols):
				if board[i][j] == 'O' and visited[i][j] == 0:
					board[i][j] = 'X'
		mat = board
		return mat