# C++ dfs 9ms clear, no additional memory

• ``````class Solution {
public:

int n,m;
int di[4]={0,-1,0,1};
int dj[4]={-1,0,1,0};

bool valid(int i, int j){
return (i>=0 && i<n && j>=0 && j<m);
}
void flood(int i, int j,vector<vector<char>>& board){
board[i][j] = '1';

for(int k=0; k<4; ++k){
int ii = i+di[k];
int jj = j+dj[k];
if(valid(ii,jj) && board[ii][jj] == 'O')
flood(ii,jj,board);
}
}

void set(vector<vector<char>>& board, char from, char to){
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
if(board[i][j] == from)
board[i][j] = to;
}

void solve(vector<vector<char>>& board){
if(board.empty())
return;
n = board.size();
m = board[0].size();

for(int i=0; i<n; ++i){
if(board[i][0] == 'O')
flood(i,0,board);
if(board[i][m-1] == 'O')
flood(i,m-1,board);
}

for(int j=0; j<m; ++j){
if(board[0][j] == 'O')
flood(0,j,board);
if(board[n-1][j] == 'O')
flood(n-1,j,board);
}

set(board, 'O', 'X');
set(board, '1', 'O');
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.