Simple C++ Boundary Conditions BFS solution


#1

int row = A.size();
int col = A[0].size();
int rowt[4]= {-1,0,1,0};
int colt[4] = {0,1,0,-1};
queue<pair<int,int>> q;
vector<vector> vis(row, vector (col,1));

for(int i=0;i<row;i++)
{
if(A[i][0] == ‘O’) q.push({i,0});
if(A[i][col-1] == ‘O’) q.push({i,col-1});
}
for(int i=1;i<col-1;i++)
{
if(A[0][i] == ‘O’) q.push({0,i});
if(A[row-1][i] == ‘O’) q.push({row-1,i});
}
while(!q.empty())
{
pair<int,int> t = q.front();
q.pop();
int x1 = t.first;
int x2 = t.second;
vis[x1][x2] = false;
for(int i=0;i<4;i++)
{
int x = x1+rowt[i];
int y = x2+colt[i];
if(x>=0 && x<row && y>=0 && y<col && vis[x][y] && A[x][y] == ‘O’) q.push({x,y});
}
}
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(vis[i][j]) A[i][j] = ‘X’;
}
}