Started from the ends


#1

int n,m;
vector<vector >v;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
void dfs(int x,int y)
{
v[x][y] = 2;
for(int i = 0;i<4;i++)
{
int xx = x+dx[i];
int yy = y+dy[i];
if(xx>=0 && yy>=0 && xx<n && yy<m && v[xx][yy] == 0)
dfs(xx,yy);
}
}
void Solution::solve(vector<vector > &A) {
n = A.size();
m = A[0].size();
v.resize(n);
for(int i = 0;i<n;i++)
{
v[i].clear();
v[i].resize(m,0);
for(int j = 0;j<m;j++)
{
v[i][j] = (A[i][j]==‘X’);
}
}
for(int i = 0;i<n;i++)
{
if(A[i][0]==‘O’ && v[i][0]==0)
dfs(i,0);
if(A[i][m-1]==‘O’ && v[i][m-1]==0)
dfs(i,m-1);
}
for(int i = 0;i<m;i++)
{
if(A[0][i]==‘O’ && v[0][i]==0)
dfs(0,i);
if(A[n-1][i]==‘O’ && v[n-1][i]==0)
dfs(n-1,i);
}
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
// cout<<v[i][j]<<" ";
if(v[i][j] ==0)A[i][j] = ‘X’;
}
}

}