Dsa
Union Find
Easy
Island Connection
In a grid representing several islands and ocean, each cell can either be land or water. Given a grid and the coordinates of land cells, your task is to determine how many distinct islands are in the grid, where an island is formed by horizontally or vertically adjacent land cells.
Input:
The first line contains two integers r and c (1 ≤ r, c ≤ 100), representing the number of rows and columns in the grid. The next line contains an integer n (1 ≤ n ≤ 100) representing the number of land cells. The next n lines contain two integers x and y (1 ≤ x ≤ r, 1 ≤ y ≤ c), indicating the coordinates of land cells in the grid.
Output:
Print the number of distinct islands formed by the land cells.
Example:
Input:
3 3
5
1 1
1 2
2 2
3 3
2 3
Output:
2
Key concepts
union_findgridislands
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now