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[0].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[0].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” ]