C++ dfs solution with areas


#1

int surr_pos[][2]={{0,-1},{-1,0}, {1,0},{0,1}};

bool dfs(vector<vector > &A,
int i,
int j,
vector<vector>& visited,
vector <pair<int, int>>& area)
{
bool result = false;
if (i < 0 || j < 0 || i>= A.size() || j >= A[i].size())//check if valid cell
return result;

 if (visited[i][j] || A[i][j] != 'O') return result; //skip visited and not O
 
 visited[i][j] = true;//mark as visited
 area.push_back(make_pair(i,j));
 
 if (i ==0 || j == 0 || i == A.size()-1 || j == A[i].size()-1) // on border
   result |=true;
 
 // continue to  look for connected points
 
 for (auto& cell : surr_pos)
 {
     result |=dfs(A, i + cell[0], j + cell[1], visited, area);
 }
 
 return result;

}

void Solution::solve(vector<vector > &A) {
vector<vector> visited;
for(auto row : A)
{
vector v_row;
for(auto c : row)
{
v_row.push_back(false);
}
visited.push_back(v_row);
}

vector <vector <pair<int, int>>> to_flip;
for(int i = 0 ; i< A.size();++i)     
{
    for(int j = 0; j < A[i].size();++j)
    {
        if (A[i][j] == 'O' && !visited[i][j]) //try to find area with it
        {
            vector <pair<int, int>> area;
            bool isOnBorder  = dfs(A, i, j, visited, area);
            if (isOnBorder == false)
            {
                to_flip.push_back(area);
            }
        }
    }
}
//flip
for(auto& area : to_flip)
 for (auto& cell : area)
 {
     A[cell.first][cell.second]='X';
 }

}