What is the time complexity for this modified BFS code?

Правка en1, от _Satoru_, 2022-10-06 23:22:10

I am trying to figure out the time complexity of this code https://leetcode.com/submissions/detail/816740998/ for this problem on leetcode https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/ . Since after each update we are pushing the node to the queue again I am not able to convince myself that the time complexity is O(nm). How can we prove that each cell will be updated constant times?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский _Satoru_ 2022-10-07 11:46:44 38
en2 Английский _Satoru_ 2022-10-07 07:21:45 2311
en1 Английский _Satoru_ 2022-10-06 23:22:10 466 Initial revision (published)