StraightForward graph dfs on grid solution


#1

int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
bool isSafe(int i,int j,int pos,vector &A, string B)
{
int n=A.size(); int m=A[0].length();
if(i<0 || j<0 || i>=n || j>=m || pos>=B.length() || A[i][j]!=B[pos])
return false;
return true;
}
bool dfs(int i,int j,int pos,vector &A, string& B)
{
if(pos==B.length()-1)return true;
bool result=false;
for(int k=0;k<4;k++)
{
int x=i+dx[k]; int y=j+dy[k];
if(isSafe(x,y,pos+1,A,B))
result=(result || dfs(x,y,pos+1,A,B));
}
return result;
}
int Solution::exist(vector &A, string B) {
int n=A.size(); if(n==0)return false;
int m=A[0].length();
if(B.length()==0)return 1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(A[i][j]==B[0])
if(dfs(i,j,0,A,B))
return 1;
}
}
return false;
}