Đếm tàu
Gửi bài giải
Điểm:
50
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Tác giả:
Kiểu bài tập
Ngôn ngữ cho phép
C++, Python
Trên biển có một mạng lưới hình chữ nhật gồm nhiều ô vuông. Mỗi ô được biểu diễn bởi một trong hai ký tự:
#: ô có chứa một phần của một con tàu;.: ô không chứa tàu.
Mỗi con tàu có dạng một hình chữ nhật, tức là tất cả các ô tạo thành con tàu nằm trên một số hàng liên tiếp và một số cột liên tiếp.
Hai con tàu khác nhau không chạm nhau theo cạnh. Nói cách khác, không tồn tại hai ô # thuộc hai con tàu khác nhau có chung một cạnh.
Yêu cầu: Hãy xác định số lượng con tàu có trên biển.
INPUT
Dữ liệu gồm nhiều dòng, mỗi dòng là một xâu ký tự biểu diễn một hàng của mạng lưới. Các dòng được đảm bảo có cùng độ dài.
OUTPUT
In ra một số nguyên duy nhất là số lượng con tàu có trên biển.
Ràng buộc
- 1 ≤ số dòng ≤ 2000;
- 1 ≤ số cột ≤ 2000;
- Mỗi dòng chỉ chứa hai ký tự
.và#; - Hai con tàu bất kỳ không có ô nào chung cạnh;
- Mỗi con tàu là một hình chữ nhật;
- Có ít nhất một con tàu.
Ví dụ
Sample Input
.###
....
##..
##..
..#.
..#.
Sample Output
3
Giải thích
Mạng lưới có 3 con tàu:
- Con tàu thứ nhất gồm 3 ô
#liên tiếp trên hàng đầu tiên; - Con tàu thứ hai là một hình chữ nhật kích thước
2 × 1; - Con tàu thứ ba là một hình chữ nhật kích thước
2 × 1.
Các con tàu không chạm nhau theo cạnh.
Vì vậy, số lượng con tàu là:
3
Nhận xét