Spring CodeSprint Editorials Revealed!
1. Connected Cell in a Grid
As you may have guessed, knowledge of graphs is crucial in solving this challenge.
Simply treat the grid as a graph where each cell with a '1' is connected to another cell with a '1', if they are adjacent either diagonally or vertically or horizontally.
Use standard DFS (depth first search) algorithm, but modify it to assign a unique number to each cell identified in a connected component. Since the cells are originally numbered with 0 and 1, when we begin the DFS, the first visited cell is marked '2', the next one '3' and so on (just to avoid confusion with the original '1s' in the cells).
Read full article from Spring CodeSprint Editorials Revealed!
No comments:
Post a Comment