#include<iostream>
using namespace std;
int main()
{
void fun(int,int,int,int,float*,float*,int,int);
int m,n,x,y,N;
float a=0.0,b=0.0,*p=&a,*q=&b;
cin>>m>>n>>x>>y>>N;
fun(m,n,x,y,p,q,0,N);
cout<<(*q)/((*q)+(*p));
}
void fun(int m,int n,int x,int y,float *p,float *q,int S,int N)
{
if(S==N && x>=0 && y>=0 && x<m && y<n)
{
(*q)++;
return;
}
else if((S<=N) && (x<0 || y<0 || x>=m || y>=n))
{
(*p)++;
return;
}
else
{
fun(m,n,x+1,y,p,q,S+1,N);
fun(m,n,x-1,y,p,q,S+1,N);
fun(m,n,x,y+1,p,q,S+1,N);
fun(m,n,x,y-1,p,q,S+1,N);
}
}
A blog on programming and software design interview problems and solutions. Also there are some application development related stuff.
Pages
Wednesday, August 29, 2012
Grid Traversal
There is a rectangular grid of size m * n . Bob is in location ( x, y ) inside grid. He can move in 4 directions up, down, right and left. He will die if he steps outside of rectangular grid. Find the probability that bob is alive given initial position of bob as ( x, y ) and number of steps he moves as N. (Given that Bob moves only one step at a time).
Subscribe to:
Post Comments (Atom)
Can you give a clarification on the question? Can bob choose his steps or does he walk randomly? Can he repeat himself or cross over the same node twice?
ReplyDeleteYes sure. Bob can choose to step either to the left, right, top or bottom node from the current node (i.e. the node which he is standing at a particular moment). Yes he can repeat himself or cross over the same node any number of times as long as he has not stepped N times.
ReplyDeleteExecutives at SAS software, based in Buckinghamshire, say the use of computer infrastructure or networks.
ReplyDeleteAlso sometimes referred to as a" phablet" half-phone, half-tablet, the
Note is noteworthy see what I did through the power of Jesus Christ.