27 Apr 2014

Maze: Count all possible paths

Problem Statement:
       Count all the possible paths in the given maze.
            Note: Only right and bottom moves allowed.


Solution: 
Run Source Code     
   We would using recursion to count the possible pats, as (N-1,N-1) is reached count is incremented each time.

Below is logic implemented.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Find count of possible paths in the maze
 * @author PRATEEK
 */
public class CountPaths {

 private static int rowLen, colLen, count;
 public static void paths(int[][] maze, int row, int col) {
  if (row == rowLen && col == colLen) {
   count++;
   return;
  }
  /*// move left
  if (col > 0 && maze[row][col - 1] == 1)
   paths(maze, row, col - 1);*/

  // move right
  if (col < colLen && maze[row][col + 1] == 1)
   paths(maze, row, col + 1);

  /*// move up
  if (row > 0 && maze[row - 1][col] == 1)
   paths(maze, row - 1, col);*/

  // move down
  if (row < rowLen && maze[row + 1][col] == 1)
   paths(maze, row + 1, col);

 }

 public static void main(String[] args) {
  int[][] maze = { 
    {1, 1, 0, 0, 1, 1 }, 
    {1, 1, 1, 1, 0, 0 },
    {1, 0, 0, 0, 1, 0 }, 
    {1, 1, 1, 1, 0, 0 },
    {1, 0, 1, 0, 0, 0 },
    {1, 1, 1, 1, 1, 1 }
  };
  
  rowLen = maze.length-1;
  colLen = maze[0].length-1;
  
  paths(maze,0,0);
  System.out.println("Number of Paths: "+count);
 }
}

Please comment and post your suggestions.
Happy Coding !! :)

10 comments:

  1. Is the audience still comprised of decision makers. If you currently have
    a trade exhibition booth designed, get it ready for a full analysis.
    Visit your customers' Facebook pages and personally invite the crooks to
    stop by and visit your display displays and banner stands.



    my weblog - portable display system ()

    ReplyDelete
  2. Is the viewers still made up of decision makers.
    But, reaching out to the target market, instilling interest one of them, was difficult since there was no
    definitive means of promoting the brand or business via
    brochures. Visit your customers' Facebook pages and personally
    invite these phones stop by and visit your trade show displays and
    banner stands.

    my weblog :: discount portable booth displays

    ReplyDelete
  3. Some birds, by way of example will embark on singing displays that mirror
    the motions in the grass display like the Cutthroat finch.
    If your unit is not modular, contact the company before you make any structural changes.
    If the consumer had to get a display, it will either should be a
    one-size-fits-all model, or they may have to purchase
    several different sized exhibits.

    Also visit my site; buy display panels

    ReplyDelete
  4. Is the crowd still consists of decision makers. If your unit is just not modular, contact the business before you make
    any structural changes. Three popular raffle drum trends you have probably affecting action are fabricated from either steel,
    clear acrylic, or some other form of plastic known as PETG.


    Here is my weblog :: cheap convention displays

    ReplyDelete
  5. Hey there! I know this is kinda off topic but I wass wondering which
    blog platform are you using for this website?
    I'm getting sick andd tired off Wordpress because I've hhad
    problems with hackers and I'm looking at options for another platform.

    I would be awesome if you could point me in the direction of a good platform.


    Also visit my web site - Las Vegas Dryer Parts

    ReplyDelete
  6. Great blog! Do you have any suggestions for aspiring writers?
    I'm hoping to start my own website soon but I'm a little
    lost on everything. Would you recommend starting with a free platform like Wordpress or go for a paid option? There are so many options out there that I'm completely overwhelmed ..

    Any recommendations? Appreciate it!

    Check out my website price private jet

    ReplyDelete
  7. Great site. Plenty of helpful info here. I'm sending
    it to several friends ans additionally sharing in delicious.
    And of course, thanks for your sweat!

    Feel free to visit my webpage: hiring private jet

    ReplyDelete
  8. you are actually a good webmaster. The site loading pace is incredible.
    It sort of feels that you're doing any unique trick.
    Furthermore, The contents are masterwork. you
    have done a excellent task in this topic!

    My web site ... seo company offer

    ReplyDelete
  9. Truly no matter if someone doesn't be aware of after that its up to other users that they will help, so here it happens.


    My web page: rent a private jet cost

    ReplyDelete