 # DFS solution C++

#1

bool AddToArea(vector<vector > &A, int x, int y, vector<pair<int,int>> &area,
vector<vector > &visited) {
int N = A.size();
int M = A.size();

``````if (visited[x][y]){
return true;
}

visited[x][y] = true;

if (x == 0 || x == N - 1 ||
y == 0 || y == M - 1) {
return false;
} else {
bool surrounded = true;
if (x>0 && y>0 & A[x-1][y-1] == 'O') {
surrounded = AddToArea(A, x-1, y-1, area, visited);
}

if (surrounded && x<N && y>0 & A[x+1][y-1] == 'O') {
surrounded = AddToArea(A, x+1, y-1, area, visited);
}

if (surrounded && x>0 && y<M & A[x-1][y+1] == 'O') {
surrounded = AddToArea(A, x-1, y+1, area, visited);
}

if (surrounded && x<N && y<M & A[x+1][y+1] == 'O') {
surrounded = AddToArea(A, x+1, y+1, area, visited);
}

if (surrounded && y>0 && A[x][y-1] == 'O') {
surrounded = AddToArea(A, x, y-1, area, visited);
}

if (surrounded && x>0 && A[x-1][y] == 'O') {
surrounded = AddToArea(A, x-1, y, area, visited);
}

if (surrounded && x<N && A[x+1][y] == 'O') {
surrounded = AddToArea(A, x+1, y, area, visited);
}

if (surrounded && y<M && A[x][y+1] == 'O') {
surrounded = AddToArea(A, x, y+1, area, visited);
}

if (surrounded) {
area.push_back(pair<int,int>(x, y));
}
return surrounded;
}
``````

}

void Solution::solve(vector<vector > &A) {
int N = A.size();
int M = A.size();
vector<vector > visited;
bool surrounded;
int x = 0;
int y = 0;
for (vector row : A){
vector visited_row;
for (char point : row) {
visited_row.push_back(false);
}
visited.push_back(visited_row);
}

``````for (vector<char> row : A){
y = 0;
for (char point : row) {
if (!visited[x][y] && point == 'O') {
vector<pair<int,int>> area;
bool surrounded = AddToArea(A, x, y, area, visited);
if (surrounded) {
for (pair<int, int> point : area) {
A[point.first][point.second] = 'X';
}
}
}
y++;
}
x++;
``````

}

}`

Summary

Preformatted text

`

#2

failed for:
[ “XOOOOOOX”, “XXOOXOOX”, “OXXOXOXX” ]