123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// DelRow and delCol for neighbors
vector<int> delRow = {-1, 0, 1, 0};
vector<int> delCol = {0, 1, 0, -1};
/* Helper Function to check if a
cell is within boundaries */
bool isValid(int &i, int &j,
int &n, int &m) {
// Return false if cell is invalid
if(i < 0 || i >= n) return false;
if(j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
// Recursive function to perform DFS
void dfs(int row, int col,
vector<vector<bool>> &vis,
vector<vector<char>> &mat,
int &n, int &m) {
// Mark the node as visited
vis[row][col] = true;
// Check the 4 neighbors
for(int i=0; i < 4; i++) {
// Determine coordinates of new cell
int nRow = row + delRow[i];
int nCol = col + delCol[i];
/* If an unvisited, valid
cell contains 'O' */
if(isValid(nRow, nCol, n, m) &&
mat[nRow][nCol] == 'O' &&
!vis[nRow][nCol] ) {
// Recursive DFS traversal
dfs(nRow, nCol, vis, mat, n, m);
}
}
}
public:
/* Function to replace
surrounded 'O's with 'X's */
vector<vector<char>>
fill(vector<vector<char>> mat) {
// Determine the dimensions of matrix
int n = mat.size();
int m = mat[0].size();
// Visited array
vector<vector<bool>> vis(n, vector<bool>(m, false));
// Traverse the boundaries
// Traversal for boundary rows
for(int j=0; j < m; j++) {
/*Check for unvisited 'O's
in boundary rows */
// First row
if(!vis[0][j] && mat[0][j] == 'O') {
// Start DFS traversal from current node
dfs(0, j, vis, mat, n, m);
}
// Last row
if(!vis[n-1][j] && mat[n-1][j] == 'O') {
// Start DFS traversal from current node
dfs(n-1, j, vis, mat, n, m);
}
}
// Traversal for boundary columns
for(int i=0; i < n; i++) {
/*Check for unvisited 'O's
in boundary columns */
// First column
if(!vis[i][0] && mat[i][0] == 'O') {
// Start DFS traversal from current node
dfs(i, 0, vis, mat, n, m);
}
// Last column
if(!vis[i][m-1] && mat[i][m-1] == 'O') {
// Start DFS traversal from current node
dfs(i, m-1, vis, mat, n, m);
}
}
/* Traverse the matrix and convert
the unvisited 'O's into 'X' */
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++) {
// Check for unvisited 'O's
if(mat[i][j] == 'O' &&
!vis[i][j]) {
mat[i][j] = 'X';
}
}
}
// return the updated matrix
return mat;
}
};
int main() {
vector<vector<char>> mat = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to replace
surrounded 'O's with 'X's */
vector<vector<char>> ans = sol.fill(mat);
int n = ans.size();
int m = ans[0].size();
// Output
cout << "The updated matrix is: " << endl;
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136
import java.util.*;
class Solution {
// DelRow and delCol for neighbors
private int[] delRow = {-1, 0, 1, 0};
private int[] delCol = {0, 1, 0, -1};
/* Helper Function to check if
a cell is within boundaries */
private boolean isValid(int i, int j,
int n, int m) {
// Return false if cell is invalid
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
// Recursive function to perform DFS
private void dfs(int row, int col,
boolean[][] vis,
char[][] mat,
int n, int m) {
// Mark the node as visited
vis[row][col] = true;
// Check the 4 neighbors
for (int i = 0; i < 4; i++) {
// Determine coordinates of new cell
int nRow = row + delRow[i];
int nCol = col + delCol[i];
// If an unvisited, valid cell contains 'O'
if (isValid(nRow, nCol, n, m) &&
mat[nRow][nCol] == 'O' &&
!vis[nRow][nCol]) {
// Recursive DFS traversal
dfs(nRow, nCol, vis, mat, n, m);
}
}
}
// Function to replace surrounded 'O's with 'X's
public char[][] fill(char[][] mat) {
// Determine the dimensions of matrix
int n = mat.length;
int m = mat[0].length;
// Visited array
boolean[][] vis = new boolean[n][m];
// Traverse the boundaries
// Traversal for boundary rows
for (int j = 0; j < m; j++) {
// Check for unvisited 'O's in boundary rows
// First row
if (!vis[0][j] && mat[0][j] == 'O') {
// Start DFS traversal from current node
dfs(0, j, vis, mat, n, m);
}
// Last row
if (!vis[n - 1][j] && mat[n - 1][j] == 'O') {
// Start DFS traversal from current node
dfs(n - 1, j, vis, mat, n, m);
}
}
// Traversal for boundary columns
for (int i = 0; i < n; i++) {
// Check for unvisited 'O's in boundary columns
// First column
if (!vis[i][0] && mat[i][0] == 'O') {
// Start DFS traversal from current node
dfs(i, 0, vis, mat, n, m);
}
// Last column
if (!vis[i][m - 1] && mat[i][m - 1] == 'O') {
// Start DFS traversal from current node
dfs(i, m - 1, vis, mat, n, m);
}
}
/* Traverse the matrix and convert
the unvisited 'O's into 'X' */
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Check for unvisited 'O's
if (mat[i][j] == 'O' && !vis[i][j]) {
mat[i][j] = 'X';
}
}
}
// Return the updated matrix
return mat;
}
public static void main(String[] args) {
char[][] mat = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'}
};
// Creating an instance of Solution class
Solution sol = new Solution();
// Function call to replace surrounded 'O's with 'X's
char[][] ans = sol.fill(mat);
int n = ans.length;
int m = ans[0].length;
// Output
System.out.println("The updated matrix is:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(ans[i][j] + " ");
}
System.out.println();
}
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
class Solution:
def __init__(self):
# DelRow and delCol for neighbors
self.delRow = [-1, 0, 1, 0]
self.delCol = [0, 1, 0, -1]
# Helper Function to check if a
# cell is within boundaries
def isValid(self, i, j, n, m):
# Return false if cell is invalid
if i < 0 or i >= n:
return False
if j < 0 or j >= m:
return False
# Return true if cell is valid
return True
# Recursive function to perform DFS
def dfs(self, row, col, vis, mat, n, m):
# Mark the node as visited
vis[row][col] = True
# Check the 4 neighbors
for i in range(4):
# Determine coordinates of new cell
nRow = row + self.delRow[i]
nCol = col + self.delCol[i]
# If an unvisited, valid cell contains 'O'
if (self.isValid(nRow, nCol, n, m) and
mat[nRow][nCol] == 'O' and
not vis[nRow][nCol]):
# Recursive DFS traversal
self.dfs(nRow, nCol, vis, mat, n, m)
# Function to replace surrounded 'O's with 'X's
def fill(self, mat):
# Determine the dimensions of matrix
n = len(mat)
m = len(mat[0])
# Visited array
vis = [[False] * m for _ in range(n)]
# Traverse the boundaries
# Traversal for boundary rows
for j in range(m):
# Check for unvisited 'O's in boundary rows
# First row
if not vis[0][j] and mat[0][j] == 'O':
# Start DFS traversal from current node
self.dfs(0, j, vis, mat, n, m)
# Last row
if not vis[n - 1][j] and mat[n - 1][j] == 'O':
# Start DFS traversal from current node
self.dfs(n - 1, j, vis, mat, n, m)
# Traversal for boundary columns
for i in range(n):
# Check for unvisited 'O's in boundary columns
# First column
if not vis[i][0] and mat[i][0] == 'O':
# Start DFS traversal from current node
self.dfs(i, 0, vis, mat, n, m)
# Last column
if not vis[i][m - 1] and mat[i][m - 1] == 'O':
# Start DFS traversal from current node
self.dfs(i, m - 1, vis, mat, n, m)
# Traverse the matrix and convert
# the unvisited 'O's into 'X'
for i in range(n):
for j in range(m):
# Check for unvisited 'O's
if (mat[i][j] == 'O' and
not vis[i][j]):
mat[i][j] = 'X'
# Return the updated matrix
return mat
# Creating an instance of Solution class
sol = Solution()
# Input matrix
mat = [
['X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X'],
['X', 'X', 'O', 'X'],
['X', 'O', 'X', 'X']
]
# Function call to replace surrounded 'O's with 'X's
ans = sol.fill(mat)
# Output
print("The updated matrix is:")
for row in ans:
print(" ".join(row))
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
class Solution {
constructor() {
// DelRow and delCol for neighbors
this.delRow = [-1, 0, 1, 0];
this.delCol = [0, 1, 0, -1];
}
/* Helper Function to check if
a cell is within boundaries */
isValid(i, j, n, m) {
// Return false if cell is invalid
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
// Recursive function to perform DFS
dfs(row, col, vis, mat, n, m) {
// Mark the node as visited
vis[row][col] = true;
// Check the 4 neighbors
for (let i = 0; i < 4; i++) {
// Determine coordinates of new cell
let nRow = row + this.delRow[i];
let nCol = col + this.delCol[i];
// If an unvisited, valid cell contains 'O'
if (this.isValid(nRow, nCol, n, m) &&
mat[nRow][nCol] === 'O' &&
!vis[nRow][nCol]) {
// Recursive DFS traversal
this.dfs(nRow, nCol, vis, mat, n, m);
}
}
}
// Function to replace surrounded 'O's with 'X's
fill(mat) {
// Determine the dimensions of matrix
let n = mat.length;
let m = mat[0].length;
// Visited array
let vis = Array.from(
{ length: n },
() => Array(m).fill(false)
);
// Traverse the boundaries
// Traversal for boundary rows
for (let j = 0; j < m; j++) {
// Check for unvisited 'O's in boundary rows
// First row
if (!vis[0][j] && mat[0][j] === 'O') {
// Start DFS traversal from current node
this.dfs(0, j, vis, mat, n, m);
}
// Last row
if (!vis[n - 1][j] && mat[n - 1][j] === 'O') {
// Start DFS traversal from current node
this.dfs(n - 1, j, vis, mat, n, m);
}
}
// Traversal for boundary columns
for (let i = 0; i < n; i++) {
// Check for unvisited 'O's in boundary columns
// First column
if (!vis[i][0] && mat[i][0] === 'O') {
// Start DFS traversal from current node
this.dfs(i, 0, vis, mat, n, m);
}
// Last column
if (!vis[i][m - 1] && mat[i][m - 1] === 'O') {
// Start DFS traversal from current node
this.dfs(i, m - 1, vis, mat, n, m);
}
}
// Traverse the matrix and convert the unvisited 'O's into 'X'
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// Check for unvisited 'O's
if (mat[i][j] === 'O' && !vis[i][j]) {
mat[i][j] = 'X';
}
}
}
// Return the updated matrix
return mat;
}
}
// Input matrix
let mat = [
['X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X'],
['X', 'X', 'O', 'X'],
['X', 'O', 'X', 'X']
];
// Creating an instance of Solution class
let sol = new Solution();
// Function call to replace surrounded 'O's with 'X's
let ans = sol.fill(mat);
// Output
console.log("The updated matrix is:");
for (let row of ans) {
console.log(row.join(" "));
}
