C11STAR - Counting Star
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Sau các kỳ thi căng thẳng, chú Bò sữa “ Milk Lucky ” được bố mẹ cho về quê chơi, xả street. Quê của chú bò là một vùng trang trại rộng ở ngoại ô thành phố, ở đây không khí trong lành, không có sự ồn ào, bụi bặm hay các tòa nhà cao tầng.
Do không bị che khuất nên bầu trời cao và rộng. Vào mỗi tối, Milk Lucky lại ra ngồi ngắm các vì sao trên trời với sự thích thú kỳ lạ. Với trí tưởng tượng phong phú của mình chú nối các vì sao lại thành các chòm sao và ghi vào cuốn sổ tay nhỏ của mình số các chòm sao chú cho là đẹp mà chú quan sát được mỗi đêm để sau này về lại thành phố khoe với bố mẹ.
Chú Bò sữa định nghĩa một “chòm sao đẹp” như sau:
- Chú bò chia không gian bầu trời mà chú bò quan sát được thành MxN ô, các ngôi sao nằm trọn vào mỗi ô trong đó và chú ký hiệu các ô có sao bằng các chữ cái in thường (“ a ”..” z ”) (các ngôi sao chú càm thấy giống nhau sẽ quy về cùng 1 ký tự)các ô có ký tự “ . ” là khoảng không vũ trụ.
- " Chòm sao đẹp” là tập hợp 4 ngôi sao cùng mã ký tự tạo thành 1 hình tứ giác mà 2 đỉnh kề của tứ giác phải cùng nằm trên 1 đường chéo (xiêng 45 độ) trong bảng.
Hôm nay Milk Lucky ngủ quên, do đó hãy giúp chú bò đếm và ghi lại giúp chú ấy đêm nay có bao nhiêu “chòm sao đẹp” nhé!
Input
- Dòng đầu chứa 2 số nguyên dương M,N (1≤M≤3000, 1≤N≤200).
- M dòng sau mỗi dòng chứa N ký tự, ký tự ‘.’ thể hiện khoảng không gian, ký tự chữ cái la tinh (‘a’..’z’) thể hiện các vì sao
Output
- In ra 1 số duy nhất là số chòm sao đẹp tính được.
Example
Input: 5 5 .a... a.ab. .abzb .bzbz ..bz. Output: 5
Giới hạn:
+ 20% số test có m, n ≤ 100.
+ 30% số test tiếp theo có m ≤ 600, n ≤ 150
+ 50% số test tiếp theo có m ≤ 3000, n ≤ 200
- Người up: yellowflash12
- Nguồn bài: C11 Contest Round 22 - Lê Hùng Sơn