[GFG] Replace O's with X's

https://practice.geeksforgeeks.org/problems/replace-os-with-xs0052/1
mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.4 kB
18
Indexable
Never
// 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;
    }
};