code.degub's blog

0-1 bfs Getting TLE Please help
By code.degub, history, 3 years ago, In English

Question In this question i am trying to use 0-1 bfs here is my code 115034044 can anyone help me to find why i am getting TLE or what's wrong in this please help

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Oh lol I tried a number of optimizations before I realized that your complexity is $$$\mathcal O(nmk)$$$ with $$$n, m, k \leq 1000$$$, which is too much.

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

    Thanks but 38798575 isn't this submission same ?

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

      That looks like an unintended solution, considering editorial says $$$\mathcal O(nmk)$$$ is supposed to be too slow. Java is considerably slower, so I'd be surprised if you can get the solution to fit.

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

your solution is correct 115077277 , I only added the line if(dis[nr][nc] < dis[cr][cc]+1)break; in your bfs . if you meet a cell that has distance less than distance your current cell +1,then you don't need to consider further since it can never be worse if you started traversing in the same direction from that cell instead .I think this simple optimization makes it O(nm) but I am not sure how to prove it

→ Reply