EGYPT's blog

Problem 'E' Chip Play CF#74 Div2
By EGYPT, 14 years ago, In English
I get TLE on testcase 16 i think my algorithm is true but i need tips to improve the speed of the algorithm

some useful hints if you will help me:

1-I use recursive function but i make global varible called ct which count the steps .
2-I mark visited cell with '#' on the same matrix.
3-I make global variable called dr ,i save the last direction on it.
so   R RRL L and last direction L i will ignore the value of the cells RRL
4-Every iteration i pick cell and make recursive call on it,i make ct=0 and i send matrix by value not by reference.

if my approach totally wrong please tell me the true approach 

Click Here to see my code
Thanks in advanced.



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

Comments Comments (4)
| Write comment?
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Try scanf instead of cin.
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
You need to find another algorithm of finding next chip. Try to find it by yourself.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks for your advice,but i ask for help. :D

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      For each cell let's keep information about the nearest chip for each direction.
      Further, for current chip you can easily find next and update info for other chips very fast.
      For example, to update info for right neighbor you just need to set left neighbor for it and it'll be left neighboor for current chip.
      So, complexity will be O(n2m2) instead of yours O(n3m3).
      → Reply