Cho ma trận nhị phân 2D grid kích thước m x n chứa '1' (đất liền) và '0' (nước biển). Hãy đếm và trả về số lượng hòn đảo.
Ví dụ 1:
Input: grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
Output: 1Định Dạng Đầu Vào (Input)
Một dòng chứa ma trận 2D grid
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là số lượng đảo
Ràng Buộc (Constraints)
1 <= m, n <= 300
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output:
1
Giải thích: 1 đảo liên thông
Ví dụ 2:
Input:
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output:
3
Giải thích: 3 đảo
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật DFS / BFS Đánh Dấu Vùng Liên Thông O(m * n)
Mỗi khi gặp '1', tăng count và gọi DFS chuyển toàn bộ đảo thành '0'.
Dữ liệu đầu vào (Input):
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Kết quả kỳ vọng (Expected Output):
1
Dữ liệu đầu vào (Input):
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Kết quả kỳ vọng (Expected Output):
3
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
