Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11STAR - Counting Star

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, n150

+ 50%  số test tiếp theo có m3000, n 200

 

5 5

.a…

a.ab.

.abzb

.bzbz

..bz.

Được gửi lên bởi:Alex & Friends
Ngày:2013-11-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:C11 Contest Round 22 - Lê Hùng Sơn

hide comments
2016-12-23 10:53:36 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/559/c11star-spoj/
2015-11-03 23:12:22
Tham khảo : http://www.oni.vn/uR57W

Blog Thuật toán SPOJ (vnspoj.blogspot.com) giúp các bạn với solution và code hơn 300 bài tại : http://www.oni.vn/uR57W
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.