Timeline for 01 Matrix is too slow when solved using DFS
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2020 at 21:50 | answer | added | Håkon Hægland | timeline score: 1 | |
| Oct 13, 2020 at 20:45 | comment | added | RootTwo | There is no reason to do a DFS. Find all the zeros, and mark them with a distance of 0. The cells up/down/left/right from them are a distance of 1, unless it already has a lower distance. The cells adjacent to the "1"s are a distance of 2, and so on until all cells are marked. Taking a look at flood fill algorithms may be helpful. | |
| Oct 11, 2020 at 21:08 | comment | added | Countingstuff | Fundamentally your problem is that you recompute things too many times. Consider what your program does on the 1000 x 1000 matrix which is all 1s except the bottom right which is a 0. If you could remember results you have computed, your approach could be performant. The bfs approach isn't just bfs, it's a bfs starting from the 0s, where you update the ops matrix as you go with candidate distances, in this way you avoid recomputations. | |
| Oct 11, 2020 at 21:00 | history | tweeted | twitter.com/StackCodeReview/status/1315396773372981249 | ||
| Oct 11, 2020 at 20:08 | history | edited | vnp | CC BY-SA 4.0 | added 144 characters in body |
| Oct 11, 2020 at 6:03 | history | asked | Akanksha | CC BY-SA 4.0 |