All possible paths for a robot moving along a NxN grid

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.

My initial thoughts:

  • Base case: f(N, 0) = 1, f(0, N) = 1
  • Recursion: f(N, N) = f(N, N-1) + f(N-1, N)

My initial codes (solution):

	public static int allPossiblePaths(int M, int N) {
		if (N == 0 || M == 0)
			return 1;
		return allPossiblePaths(M - 1, N) + allPossiblePaths(M, N - 1);
	}

	public static int AllPossiblePathsWithObstacles(int M, int N,
			Set<Pair<Integer>> obstacles) {
		if (obstacles.contains(new Pair<Integer>(M, N)))
			return 0;
		else {
			if (N == 0 || M == 0)
				return 1;
			return AllPossiblePathsWithObstacles(M - 1, N, obstacles)
					+ AllPossiblePathsWithObstacles(M, N - 1, obstacles);
		}
	}

If we would also like to print out all paths:

	public static void PrintAllPossiblePathsWithObstacles(int M, int N,
			Set<Pair<Integer>> obstacles, String path) {
		if (obstacles.contains(new Pair<Integer>(M, N)))
			return;
		else {
			if (M == 0) {
				for (int i = 0; i < N; ++i)
					path = "DOWN " + path;
				System.out.println(path);
			} else if (N == 0) {
				for (int i = 0; i < M; ++i)
					path = "RIGHT " + path;
				System.out.println(path);
			} else {
				PrintAllPossiblePathsWithObstacles(M - 1, N, 
						obstacles, "RIGHT " + path);
				PrintAllPossiblePathsWithObstacles(M, N - 1, 
						obstacles, "DOWN " + path);
			}
		}
	}
Advertisements

5 Comments (+add yours?)

  1. Murali
    Jul 08, 2012 @ 14:10:59

    One more way to look at it,
    Let us call the down move as “1” and right move as a “0” then the path should be a string containing n “1”s and n “0”s (something like this 11111111…00000…).
    The total number of permutations(without repetition) of this string is the answer. That will be (2n!) / (n! * n!).
    Print all the permutations of this string to find all possible paths

    Reply

  2. Ashu
    Sep 18, 2012 @ 01:02:10

    This code is not printing correct paths for the following Grid, where 1 is a obstacle
    0,1,0
    0,1,0
    0,0,0

    Reply

    • Ashu
      Sep 18, 2012 @ 01:05:40

      Below is the corrected code of Java, for above case as well

      ArrayList allPaths = new ArrayList();
      public void PrintAllPossiblePathsWithObstacles(int M, int N,
      int[][] obstacles, String path) {
      if (obstacles[M][N] == 1)
      return;
      else {
      if (M == 0) {
      for (int i = 0; i < N; ++i)
      {
      if(obstacles[M][i] == 1)
      return;

      path = "RIGHT " + path;
      }
      System.out.println(path);
      allPaths.add(path);
      } else if (N == 0) {
      for (int i = 0; i < M; ++i)
      {
      if(obstacles[i][N] == 1)
      return;

      path = "DOWN " + path;
      }
      System.out.println(path);
      allPaths.add(path);
      } else {
      PrintAllPossiblePathsWithObstacles(M – 1, N, obstacles, "DOWN " + path);
      PrintAllPossiblePathsWithObstacles(M, N – 1, obstacles, "RIGHT " + path);
      }
      }
      }

      Reply

  3. Ashu
    Sep 18, 2012 @ 01:11:33

    I think I came up with this finally short and crisp version of the code that works for all the cases

    ArrayList allPaths = new ArrayList();
    public void PrintAllPossiblePathsWithObstacles(int M, int N,
    int[][] obstacles, String path) {
    if (obstacles[M][N] == 1)
    return;
    else if(M == 0 && N == 0)
    System.out.println(path);
    else {
    if(M – 1>=0 )
    PrintAllPossiblePathsWithObstacles(M – 1, N, obstacles, “DOWN ” + path);
    if(N -1 >=0 )
    PrintAllPossiblePathsWithObstacles(M, N – 1, obstacles, “RIGHT ” + path);
    }
    }

    Reply

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

%d bloggers like this: