Popular Posts

  • Robot in an NXN grid
    Problem: Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. ...
  • CLRS Exercises 2.3-4 Recursive insertion sort
    Problem: Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n], we recursively sort A[1 n -1] ...
  • Kth Largest from an infinite stream
    Problem:   Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if...
  • Print BST keys in the given range
    Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i....
  • Simultaneous minimum and maximum
    How many comparisons are necessary to determine the minimum of a set of n elements? n-1 comparisions. It is not difficult to devise an ...
  • CLRS Exercises 2.3-7
    Problem: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exi...
  • Delete alternate nodes of a Linked List
    Problem: Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked lis...
  • Print Ancestors of a given node in Binary Tree
    Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the give...
  • CLRS - Problem 2.1
    Problem: Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in i...
  • CLRS Exercises 5.1-2
    Problem: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running tim...

Monday, July 18, 2011

Robot in an NXN grid

Problem:

Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot?
FOLLOW UP
Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Solution:

  • Start from (0,0)
  • Robot can take right? i.e in boundary and cell is not marked as "off limits"
  • Then take right
  • Robot can take left? i.e in boundary and cell is not marked as "off limits"
  • Then take left
  • Do these steps recursively until destination is found or no path is found.
  • return possible steps.

It can be derived in mathematical way as follows:

Result will be like this,

1 + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+..+N)
which can be written as,









Finally, it can be expressed as follows,


Complexity: O(N^2)
Code:
Posted by anantha at 7/18/2011 02:45:00 PM
Labels: , , ,

2 comments:

  1. Shweta GargJune 23, 2017 at 8:38 PM

    could you send me complete program.please send main function also it will help in understanding this code more.

    ReplyDelete
  2. UnknownJuly 25, 2017 at 3:36 PM

    please send me the code in prakhardubey95@gmail.com

    ReplyDelete

Subscribe to: Post Comments (Atom)