We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.
We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.
Time Complexity: O(m*n) m: # of buses, n: # of routes
We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.
We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.
Return an array representing the number of bricks that will drop after each erasure in sequence.
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping. Note that the erased brick (1, 0) will not be counted as a dropped brick.
For each day, hit and clear the specified brick.
Find all connected components (CCs) using DFS.
For each CC, if there is no brick that is on the first row that the entire cc will drop. Clear those CCs.