Problem
LeetCode 934, Shortest Bridge
When I answered, I first laid out all his examples in a structured way below, then started with the function just returning 0.
Running it gave n zeros, and I told him this was the first iteration. The next step was to finish the function so it returns the correct result.
While working through it, I ran into a case where the recursion wasn't controlled properly and it blew up. I fixed that myself. There was also a case where the result was wrong, and I debugged it myself by printing out info.
Solution
First, DFS to find the two islands, then BFS starting from island 1 to expand into the water.
To find an island with DFS: first use (i, j) to find a point with value 1, then DFS floodfill it to -1, and at the same time put its coordinates into a set called island1.
Then traverse the whole grid and set the remaining points with value 1 to -2. This gives us a grid with values 0, -1, and -2.
Starting the expansion from island1, set step to 0. If a neighbor is water, add it to next_expansion. If a neighbor is island 2, we get the result immediately and return step.
Discussion
Loading comments…