Simple dfs solution


#1

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

bool isValid(int dx,int dy,int r,int c,vector<vector > &A)
{
if(dx<0||dy<0||dx>=r||dy>=c)
return false;
if(A[dx][dy]==‘X’)
return false;
return true;
}

void dfs(int x,int y,int r,int c,vector<vector > &A,vector<vector> &vis,int &flag,vector<pair<int,int>>& res)
{ vis[x][y]=true;
if(x==(r-1)||y==(c-1)||x==0||y==0)
{
flag=1;
}
for(int i=0;i<4;i++)
{
int dx=x+pos[i][0];
int dy=y+pos[i][1];
if(isValid(dx,dy,r,c,A)&&vis[dx][dy]==false)
dfs(dx,dy,r,c,A,vis,flag,res);
}
res.push_back(make_pair(x,y));

}

void Solution::solve(vector<vector > &A) {
int r=A.size();
int c=A[0].size();
vector<vector> vis(r+1,vector(c+1,false));
int flag=0;
vector<pair<int,int>> res;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(isValid(i,j,r,c,A)&&vis[i][j]==false)
{
dfs(i,j,r,c,A,vis,flag,res);
if(!flag)
{
for(auto k:res)
{
A[k.first][k.second]=‘X’;
}
}
flag=0;
res.clear();
}
}
}

}