java - All possible ways to reach an ending position -

http://www.cstutoringcenter.com/problems/problems.php?id=103

for doesn't want click it, says there's stepping stone, "-" , soldier "#", soldiers can move right. if soldier behind soldier, must wait soldier move first. ending condition when soldiers reaches end.

the number of ways 2 soldier can move across 5 stepping stones.

1) ##---  #-#--  -##--  -#-#-  --##-  --#-#  ---## 2) ##---  #-#--  -##--  -#-#-  -#--#  --#-#  ---## 3) ##---  #-#--  #--#-  -#-#-  --##-  --#-#  ---## 4) ##---  #-#--  #--#-  -#-#-  -#--#  --#-#  ---## 5) ##---  #-#--  #--#-  #---#  -#--#  --#-#  ---## 

i'm using breadth first search, 5 stones, it's running within seconds, 10 stones, it's taking hours, time increasing exponentially depth. how can deal this?

my codes:

states.java

import java.util.arraylist;   public class state {     public int stones;     public soldiers[] soldiers;     public string currentstate ="";      public boolean visited = false;      public state(int stones,int numsoldiers){         system.out.println(numsoldiers);         this.stones = stones;         soldiers = new soldiers[numsoldiers];         system.out.println("length" + soldiers.length);         initstate();     }      public state(int stones,soldiers[] soldiers){         this.stones = stones;         this.soldiers = soldiers;         paintstate();     }      public void initstate(){         for(int i=0;i<soldiers.length;i++)         {             soldiers[i] = new soldiers();             soldiers[i].position =i;             currentstate+="#";         }         for(int j=soldiers.length;j<stones;j++)         {             currentstate+="-";         }     }      private void paintstate(){         for(int j=0;j<stones;j++)         {             currentstate+="-";         }         char[] statechar = currentstate.tochararray();         currentstate = "";         for(int i=0;i<soldiers.length;i++){             statechar[soldiers[i].position] = '#';         }         for(int k=0; k<statechar.length;k++){             currentstate += statechar[k];         }     }      public void printstate(){         system.out.println(currentstate);     }     public arraylist<state> getnextstates(){         arraylist<state> states = new arraylist<state>();          for(int i=0;i<soldiers.length;i++){             soldiers[] newsoldiers = new soldiers[soldiers.length];             for(int j=0;j<soldiers.length;j++){                 newsoldiers[j] = new soldiers(soldiers[j].position);             }             if(!((newsoldiers[i].position+1)==stones))             {                 if((currentstate.charat((newsoldiers[i].position+1))=='-'))                 {                 newsoldiers[i].move();                 states.add(new state(stones,newsoldiers));                 }             }          }         if(states.size()==0)         {             testsoldiers.count++;         }         return states;     }  } 

soldiers.java

public class soldiers {      int position = 0;      public soldiers(){         position =0;     }      public soldiers(int pos){         position = pos;     }      public void move(){         position ++;     } } 

testsoldiers.java

import java.util.linkedlist; import java.util.queue;   public class testsoldiers {        public static int count=0;      public static void main(string[] args){          testsoldiers t = new testsoldiers();     }     public testsoldiers()     {         state s = new state(10,3);         breadthfirsttraversal(s);         system.out.println(count);     }      public void breadthfirsttraversal(state rootnode){          queue<state> q = new linkedlist<state>();         q.add(rootnode);         while(!q.isempty()){             state n = (state)q.poll();             n.printstate();             for(state adj : n.getnextstates()){                          q.add(adj);                  }              }         }    } 

how can make consider each state once while maintaining integrity of total number of ways end (counts in testsoldiers.java)?

for of want modify parameters, it's new state(n,k) n number of stones , k number of soldiers.

memoization might come in handy.

the idea run depth-first search count number of ways current state end, , store result, already-calculated value if ever state repeated.

for instance, there 2 ways reach end -#-#-, so, storing result when there via -##--, 2 when there via #--#-.

the simplest (but far efficient) way store these have a:

map<pair<integer (position1), integer (position2)>, integer (count)> 

more generically, perhaps make pair list.

a more efficient approach have bitmap each bit corresponds whether or not there's soldier @ given position. -#-#- correspond 01010, stored in int 10 in decimal - if there more 64 stones (i.e. fit long), use bitset.