// AMAN JAIN MCA 1st YEAR 2nd SEM
// time O(N*M), space O(1)
// Approach: Basic DFS
class Solution{
public:
void makeK(vector<vector<char>>& mat, int n, int m, int i, int j) {
mat[i][j] = 'K';
if(i + 1 < n && mat[i + 1][j] == 'O') {
makeK(mat, n, m, i + 1, j);
}
if(i - 1 >= 0 && mat[i - 1][j] == 'O') {
makeK(mat, n, m, i - 1, j);
}
if(j + 1 < m && mat[i][j + 1] == 'O') {
makeK(mat, n, m, i, j + 1);
}
if(j - 1 < m && mat[i][j - 1] == 'O') {
makeK(mat, n, m, i, j - 1);
}
}
vector<vector<char>> fill(int n, int m, vector<vector<char>> mat) {
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(mat[i][j] == 'O' && (i == 0 || i == n - 1 || j == 0 || j == m - 1)) {
makeK(mat, n, m, i, j);
}
}
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(mat[i][j] == 'O') {
mat[i][j] = 'X';
}
}
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(mat[i][j] == 'K') {
mat[i][j] = 'O';
}
}
}
return mat;
}
};