Блог пользователя EGYPT

Problem 'E' Chip Play CF#74 Div2
Автор EGYPT, 13 лет назад, По-английски
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.



  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Try scanf instead of cin.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
You need to find another algorithm of finding next chip. Try to find it by yourself.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Thanks for your advice,but i ask for help. :D

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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).
      → Ответить