Yahoo Interview Question
Software Engineer / Developers#include <bits/stdc++.h>
using namespace std;
bool isPoss(int arr[8][8],vector<vector<int>> &v,int i, int j){
cout<<i<<" "<<j<<endl;
if(arr[i][j]==0)
return false;
if(i<0 || i>=8 || j<0 || j>8)
return false;
if(arr[i][j]==9)
return true;
if(v[i][j]==0){
v[i][j]=1;
return isPoss(arr,v,i+1,j)||isPoss(arr,v,i,j+1)||isPoss(arr,v,i-1,j)||isPoss(arr,v,i,j-1);
}
return false;
}
int main()
{
int arr[8][8];
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
cin>>arr[i][j];
}
}
vector<vector<int>> v(8,vector<int>(8,0));
cout<<isPoss(arr,v,0,0);
return 0;
}
what can be done here is that we need to maintain a stack.at every turn we need to create an object that stores the possible turns that can be taken at that point and also marks which turn we have selected and push that object onto the stack.also at every move forward we need to push move to stack.at a dead end turn around with two right turns and move forward with every pop of move object.as soon as we encounter a turn object,we need to analyse it and start moving it the direction not taken by us before and mark that direction also as taken. continue this until u find a cheeze .
- saumils1987 September 13, 2010if anyone has beter idea then do post it here and do comment on the idea suggested.