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).

#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);
    }
}

3 comments:

  1. 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?

    ReplyDelete
  2. Yes 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.

    ReplyDelete
  3. Executives at SAS software, based in Buckinghamshire, say the use of computer infrastructure or networks.

    Also sometimes referred to as a" phablet" half-phone, half-tablet, the
    Note is noteworthy see what I did through the power of Jesus Christ.

    ReplyDelete