RU | EN | FR | JP | DE | CH | KR
Given a lake map represented as a two-dimensional array, where each cell is either water ('W') or land ('L'), the task is to determine the number of individual islands on this map. An island is defined as a group of adjacent (connected vertically or horizontally) land cells surrounded by water.
Example lake map:
[ ['W', 'L', 'W', 'W'], ['W', 'L', 'L', 'W'], ['W', 'W', 'L', 'W'], ['L', 'W', 'W', 'L'] ]
Expected result: There are 3 separate islands on the map. One island consists of two adjacent 'L' cells in the second column, the second one consists of one cell in the third row, third column, and the third one consists of two non-diagonally adjacent cells in the last row.
- Develop an algorithm using breadth-first search (BFS) to determine the number of islands on the map.
- Visualize the search process by marking visited and checked cells.
- Count the number of steps (movements) taken during the search process.
- Initialize an island counter and an empty queue for BFS.
- Iterate through each cell on the map.
- If the current cell is land and has not been visited yet, initiate BFS to search for an island.
- During BFS, mark visited cells and increment the step counter.
- BFS terminates when we traverse all adjacent cells of the current island.
- Repeat steps 3-5 for all cells on the map.
During the execution of the algorithm, we will visualize visited and checked cells. This will help to visually represent the process of searching for islands on the map.
After completing the algorithm, we will obtain the number of individual islands on the lake map and the number of steps (movements) taken during the search process.
This project is licensed under the MIT License - see the LICENSE file for details.