krishan's blog

SPOJ PROBLEM:cleaning robot http://www.spoj.com/SPOJ/problems/CLEANRBT/

By krishan, 9 years ago, In English

How can i approach this problem using graphs and dynamic programming? Brute force is giving TLE. I am trying to find the all the distance from '*' to each other and then finding the minimum distance.but it's not working? Can anyone please help?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can solve this problem by using travel salesman algorithm .

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please explain a little bit?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      1-first you make 2D array has all shortest path between dirty tiles in addition to start position of robot by using BFS.

      2-make dp[][] contain the element you stand on it and mask of elements refer to which dirty tiles became clean and which still dirty.

      int num_of_dirty_tiles;

      int solve(int stand,int mask){

      if(mask==(1<<num_of_dirty_tile)-1) // mean that all dirty tiles changed to clean riles.

  return 0;

 if(dp[stand][mask]!=-1)
   return dp[stand][mask];

      int a=MAX;

      for(int i=0;i<num_of_dirty_tiles;i++){

   if((1<<i&mask==0))// it mean that the tile i still dirty

     a=Min(a,solve(i,mask|(1<<i))+shortPath[stand][i]);//it take the min 
     between paths from standing tile to any dirty tile .



 }

return dp[stand][mask]=a;

      }

      }

      I hope to understand something from this algorithm .

      → Reply