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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        public static int totalNumberOfMoves = 2;
        public static int allPossibleTraversals = 0;
        public static int favorableTraversals = 0;
        static void Main(string[] args)
        {
            if (totalNumberOfMoves > 0)
            {
                int[,] inputMatrix = new int[,]
                {
                    { 0, 0, 0 },
                    { 0, 1, 0 },
                    { 0, 0, 0 }
                };
                //Determining the start position
                int startRow = -1;
                int startCol = -1;
                for (int i = 0; i < inputMatrix.GetLength(0); i++)
                {
                    for (int j = 0; j < inputMatrix.GetLength(1); j++)
                    {
                        if (inputMatrix[i, j] == 1)
                        {
                            startRow = i;
                            startCol = j;
                        }
                    }
                }
                matrixTraversal(inputMatrix, startRow, startCol, 0);
                Console.WriteLine("Favorable = " + favorableTraversals);
                Console.WriteLine("All possible traversals = " + allPossibleTraversals);
                Console.WriteLine("Probability = " + (float)favorableTraversals / allPossibleTraversals);
            }
            else
            {
                Console.WriteLine("There are no moves to be made!!!");
            }
        }

        public static void matrixTraversal(int[,] inputMatrix, int row, int col, int move)
        {
            if (move == totalNumberOfMoves)
            {
                move--;
                allPossibleTraversals++;
                if (col < 0 || col == inputMatrix.GetLength(1) || row < 0 || row == inputMatrix.GetLength(0))
                {
                    favorableTraversals++;
                }
                return;
            }

            if (col < 0 || col == inputMatrix.GetLength(1) || row < 0 || row == inputMatrix.GetLength(0))
            {
                favorableTraversals++;
                allPossibleTraversals++;
                move--;
                return;
            }

            if (move < totalNumberOfMoves)
            {
                //Move Left
                matrixTraversal(inputMatrix, row, col - 1, move + 1);
                //Move Right
                matrixTraversal(inputMatrix, row, col + 1, move + 1);
                //Move Top
                matrixTraversal(inputMatrix, row - 1, col, move + 1);
                //Move Bottom
                matrixTraversal(inputMatrix, row + 1, col, move + 1);
            }
        }
    }
}

Output
=======
Favorable = 4
All possible traversals = 16
Probability = 0.25
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s