Khoang bảo trì trong nhà máy

Bối cảnh và bài toán

Sơ đồ một khu bảo trì được biểu diễn bởi lưới. Ô '.' là lối đi, '#' là vách. Hai ô lối đi cùng một khoang nếu đi được giữa chúng bằng các bước lên, xuống, trái, phải.

Yêu cầu

Đếm số khoang liên thông trên bản đồ.

Input

Dòng đầu n, m; sau đó n dòng, mỗi dòng m ký tự '.' hoặc '#'.

Output

In ra số khoang.

Ràng buộc

• 1 <= n,m <= 1000 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n,m <= 30 | 01–04 | | S2 | 60 | Không có ràng buộc bổ sung | 05–10 |

Ví dụ 1

Input

5 8
########
#..#...#
####.#.#
#..#...#
########

Output

3

Giải thích. Các ô sàn được gom theo liên thông 4 hướng; số nhóm thu được chính là số khoang.

Ví dụ 2

Input

3 3
...
...
...

Output

1

Giải thích. Các ô sàn được gom theo liên thông 4 hướng; số nhóm thu được chính là số khoang.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Counting Rooms. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.