Đếm số hòn đảo

Trung bình

đồ thịBFS/DFSlưới5 test · 3 giây

Bản đồ n × m gồm # (đất) và . (nước). Một hòn đảo là nhóm ô đất nối với nhau theo 4 hướng (lên, xuống, trái, phải). Đếm số hòn đảo.

Với mỗi ô đất chưa thăm, loang BFS/DFS để đánh dấu cả đảo. Lưu ý: DFS đệ quy với lưới 1000×1000 có thể tràn stack — nên dùng BFS hoặc stack tự quản.

Dữ liệu vào

Dòng 1: n m (1 ≤ n, m ≤ 1000).

n dòng, mỗi dòng m ký tự # hoặc ..

Số hòn đảo.

Input

4 5
##..#
#...#
..#..
....#

Output

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.