Counting Star

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem source:
C11 Contest Round 22 - Lê Hùng Sơn
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

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 ~M \times N~ ô, 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.

image

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 \leq M \leq 3000~, ~1 \leq N \leq 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.

Giới hạn

  • ~20\%~ số test có ~m~, ~n \leq 100~.
  • ~30\%~ số test tiếp theo có ~m \leq 600~, ~n \leq 150~
  • ~50\%~ số test tiếp theo có ~m \leq 3000~, ~n \leq 200~

Sample Input

5 5
.a...
a.ab.
.abzb
.bzbz
..bz.

Sample Output

5

Comments

Please read the guidelines before commenting.



  • 0
    tuankiet17ti  commented on 11, Jan, 2022, 22:59

    Admin có thể kiểm tra lại máy chấm bài này không ạ? Em nộp ở spoj thì 100 nhưng nộp bên đây thì còn không chạy được test ví dụ.